> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/difficult-economic-situation.md).

# Difficult Economic Situation

The difficult economic situation in the country and reductions in government agricultural subsidy funding have caused Mirko to change his career again, this time to a thief. His first professional endeavour is a jewellery store heist.

The store contains N pieces of jewellery, and each piece has some mass Mi and value Vi. Mirko has K bags to store his loot, and each bag can hold some maximum mass Ci. He plans to store all his loot in these bags, but **at most one** jewellery piece in each bag, in order to reduce the likelihood of damage during the escape.

Find the maximum total jewellery value that Mirko can "liberate".

**Input**

The first line of input contains two numbers, N and K (1≤N,K≤300000).

Each of the following N lines contains a pair of numbers, Mi and Vi (1≤Mi,Vi≤1000000).

Each of the following K lines contains a number, Ci (1≤Ci≤100000000).

All numbers in the input are positive integers.

**Output**

The first and only line of output must contain the maximum possible total jewellery value.

**Scoring**

In test data worth at least 50% of total points, N and K will be less than 5000.

**Sample Input 1**

```
2 1
5 10
100 100
11
```

**Sample Output 1**

```
10
```

**Sample Input 2**

```
3 2
1 65
5 23
2 99
10
2
```

**Sample Output 2**

```
164
```

**Explanation**

Mirko stores the first piece of jewellery into the second bag and the third piece into the first bag.

```java
class Main {
    static class Pair {
        int val, index;

        Pair(int val, int index) {
            this.val = val;
            this.index = index;
        }
    }

    public static long maxJewelery(int n, int[][] jewels, int k, int[] bags) {
        // Sorting jewels on the basis of their value
        Arrays.sort(jewels, (a, b) -> b[1] - a[1]);
        // Using pair class because 2 bags can have the same capacity
        // and the set will count them as one (if we only store integer)
        // So storing with index, will help us seprate the 2 bags
        TreeSet<Pair> bagSet = new TreeSet<>((a, b) -> a.val == b.val ? a.index - b.index : a.val - b.val);
        for (int i = 0; i < bags.length; i++)
            bagSet.add(new Pair(bags[i], i));
        long ans = 0;
        for (int[] jewel : jewels) {
            // Finding the bag with capacity just >= this capacity
            // We also could not have used just indices in treeSet, because we cant sort on
            // bases of bag[i] value, but then we also need to serach according to weight of
            // jewel
            Pair bag = bagSet.ceiling(new Pair(jewel[0], 0));
            if (bag == null)
                continue;
            ans += jewel[1];
            bagSet.remove(bag);
        }
        return ans;
    }
}
```