Description

MoonLight was a little careless sometime,and have made N bugs in his program.Each bug is described by two values: points and fixTime. There are only M days left before the deadline. Each day has a corresponding workTime, and a bug can be fixed on that day if the bug's fixTime is less than or equal to workTime. No more than one bug can be fixed in a single day, and no bug fix can span more than a single day. It seems a little difficult to determine the fixing orders of these bugs.Moonlight wants to get as many points as he could.He is lazy to do it by himself,so he calls the clever man DK for help. Unfortunately, DK is busy with the entrance exams for postgraduate schools.As wisdom as you are,could you help MoonLight to maximize the sum of the points of bugs you fix?

Input

The input contains multiple test cases. For each case,first line input N M (2<=N,M<=10,000),N is the number of bugs and M is the number of days left.Followed by N lines each contains two integer Pi Ti (1<=Pi,TI<=100,000) denoting the points and fix time of the ith bug.Then following M lines each line contains only one integer Wi (1<=Wi<=100,000) denoting the work time of the ith day.

Output

For each case determine a strategy that maximizes the sum of the points of the bugs you fix, and print this sum in a single line.

Sample

Input

2 1
5 3
20 20
15
3 2
5 3
20 20
6 15
25
15

Output

5
26

Source: moonlight