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.

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;
    }
}