9044: Nazrin the Greeeeeedy Mouse

There're $n$ cheeses in the house. The $i$-th cheese is between point $i$ and point $i+1$. The $i$-th cheese's size is aia_iai and its weight is bib_ibi.
Nazrin is at point $1$ in the beginning and wants to steal some cheeses. She has $m$ chances to take the cheeses:
In the $i$-th time, Nazrin brings a bag of size szisz_iszi. Since she's greedy, for $i>1$, szi≥szi−1sz_i\ge sz_{i-1}szi≥szi−1 always holds. She can travel from point $1$ and take some cheeses. She can only travel from point $x$ to $x+1$, or backwards. If she wants to travel from point $x$ to point $x+1$, she has to dig a hole on the $x$-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 $i$-th time can't be larger than szisz_iszi. After taking the cheeses, she needs to go back to point $1$.
Please maximize the sum of the weights of taken cheeses and output it.

The first line contains two integer $n$ ($1\le n\le 200$) and $m$ (1≤m≤1051\le m\le 10^51≤m≤105).
For the following $n$ lines, the $i$-th line contains two integers aia_iai (1≤ai≤2001\le a_i\le 2001≤ai≤200) and bib_ibi (1≤bi≤1051\le b_i\le 10^51≤bi≤105).
The next line contains $m$ integers, the $i$-th one is szisz_iszi (1≤szi≤2001\le sz_i\le 2001≤szi≤200). Notice that for $i>1$, szi≥szi−1sz_i\ge sz_{i-1}szi≥szi−1.

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