In her chemistry class, Ms. Chong decides to troll her students. She injects some low-concentrated bases into the pH indicator so that it appears purple. However, once the liquid is mixed with the acidic lemon juice, the indicator will turn colourless. Ignorant of this fact, Ms. Chong's students look forward to seeing purple lemons. You, as the only student in the class who sees through Ms. Chong's trick, want to troll your teacher back. You decide to make Ms. Chong over-inject the number of bases to turn the lemon purple. You prepared an infinite amount of $N$ different types of bases for Ms. Chong. The base with type $i$ has a volume of $v_i$ mL and a base value of $b_i$. Each minute, Ms. Chong is going to add up to $t_i$ mL of bases into the lemon. The base value of the lemon at the $m^{th}$ minute is the sum of the base value of all the bases that Ms. Chong added in the first $m$ minutes. Determine the maximum base value that Ms. Chong can add to the lemon in $M$ minutes.

Constraints

$1\le N,M\le 10$

$1\le v_i\le {10}^3$

Subtask 1 [40%]

$1\le t_i,b_i\le {10}^3$

Subtask 2 [60%]

$1\le t_i\le {10}^6$

$0\le b_i\le {10}^4$

Input Specification

The first line will contain two space-separated integers, $N$ and $M$.

The second line will contain $M$ space-separated integers, $t_1,t_2,\dots ,t_M$, respectively.

The next $N$ lines will contain two space-separated integers, $v_i$ and $b_i$.

Output Specification

Output the maximum amount of base Ms. Chong can add to a lemon in $M$ minutes.

Sample Input

3 3
2 3 5
3 3
4 5
5 8

Sample Output

11