There're cheeses in the house. The -th cheese is between point and point . The -th cheese's size is and its weight is .
Nazrin is at point in the beginning and wants to steal some cheeses. She has chances to take the cheeses:
In the -th time, Nazrin brings a bag of size . Since she's greedy, for , always holds. She can travel from point and take some cheeses. She can only travel from point to , or backwards. If she wants to travel from point to point , she has to dig a hole on the -th cheese or take it. She can't take a cheese with a hole on it. Of course, the sum of the cheeses' size she takes in the -th time can't be larger than . After taking the cheeses, she needs to go back to point .
Please maximize the sum of the weights of taken cheeses and output it.

The first line contains two integer  () and  ().
For the following  lines, the -th line contains two integers  () and  ().
The next line contains  integers, the -th one is  (). Notice that for , .

One integer, the maximum sum of the weights of taken cheeses.

5 3
2 10
2 5
1 22
3 7
6 8
1 3 7

44

In the example, Nazrin can take actions below to maximize the weight of taken cheeses:

In the first time, Nazrin stays at point  and gives up the first chance to take cheese.

In the second time, Nazrin takes the cheese between point  and point  and returns to point .

In the third time, Nazrin takes all cheeses between point  and point , and goes back to point .