Incredible Okashi Inc. is a company that produces "incredible okashi" (incredibly delicious sweets). We will refer to it as the IOI company. The IOI company has made special IOI Manju (steamed buns) and has decided to sell them. The IOI company has produced $M$ types of Manju, one of each. All $M$ produced Manju are the same size, but since each has a different flavor, their prices vary. The price of the $i$-th ($1 \le i \le M$) Manju is $P_i$ yen.

By the way, do you know the Just Odd Inventions company? The business of this company is to create "just odd inventions." We will refer to it as the JOI company. The IOI company has decided to order high-quality boxes for packing the Manju from the JOI company. There are $N$ types of boxes produced by the JOI company. The $j$-th ($1 \le j \le N$) box has a size that can hold at most $C_j$ Manju, and its selling price is $E_j$ yen. The IOI company decided to order some number of these $N$ types of boxes (between 0 and $N$ types, one of each) and sell the Manju in sets by packing them into these boxes. The price of each Manju set is the sum of the prices of the Manju contained within it.

Assuming all Manju sets are sold, what is the maximum profit the IOI company can obtain? Here, profit is defined as the value obtained by subtracting the total price of the ordered boxes from the total price of the sold Manju sets. Note that any Manju not packed into boxes will be enjoyed by the IOI company staff, so they do not affect the profit.

Task

Given the price of each Manju and the size and price of each box, write a program to calculate the maximum profit the IOI company can obtain.

Input

Read the following data from standard input:

• The first line contains two space-separated integers $M$ and $N$, representing that there are $M$ Manju and $N$ types of boxes.
• The $i$-th line of the following $M$ lines ($1 \le i \le M$) contains an integer $P_i$, representing that the price of the $i$-th Manju is $P_i$ yen.
• The $j$-th line of the following $N$ lines ($1 \le j \le N$) contains two space-separated integers $C_j$ and $E_j$, representing that the $j$-th box can hold at most $C_j$ Manju and its price is $E_j$ yen.

Output

Output the maximum profit the IOI company can obtain as an integer in yen on a single line.

Constraints

All input data satisfies the following conditions:

• $1 \le M \le 10\,000$.
• $1 \le N \le 500$.
• $1 \le P_i \le 10\,000$ ($1 \le i \le M$).
• $1 \le C_j \le 10\,000$ ($1 \le j \le N$).
• $1 \le E_j \le 10\,000$ ($1 \le j \le N$).

Subtasks

Subtask 1 [25 points]

• $N \le 10$ is satisfied.

Subtask 2 [35 points]

• $C_j \le 10$ ($1 \le j \le N$) is satisfied.

Subtask 3 [40 points]

• There are no additional constraints.

Examples

Input 1

4 3
180
160
170
190
2 100
3 120
4 250

Output 1

480

Note 1

In this example, if you order the 1st box (100 yen) and the 2nd box (120 yen), and for example, pack the 1st and 2nd Manju into the 1st box to sell as a set for $180 + 160 = 340$ yen, and pack the 3rd and 4th Manju into the 2nd box to sell as a set for $170 + 190 = 360$ yen, the IOI company's profit becomes $700 - 220 = 480$ yen.

Input 2

2 2
1000
2000
1 6666
1 7777

Output 2

0

Note 2

In this example, it is better not to buy any boxes to maximize profit.

Input 3

10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600
1 900

Output 3

450