Problem Description

Incredible Okashi Inc. is a company that produces "incredible okashi" (delicious snacks). Hereafter, we will refer to it as IOI Corporation. IOI Corporation has produced a special IOI Manju and decided to sell it. IOI Corporation has made $ M $ types of manju, one of each type. The $ M $ manju are all of the same size, but each has a different flavor, so their prices vary. The price of the $ i $th ($1 \leq i \leq M$) manju is $ P_i $ yen.

By the way, are you familiar with Just Odd Inventions Inc.? This company's business is to create "just odd inventions". Hereafter, we will refer to it as JOI Corporation. IOI Corporation has decided to order high-quality boxes for packing the manju from JOI Corporation. JOI Corporation produces $ N $ types of boxes for manju. The $ j $th ($1 \leq j \leq N$) box can hold up to $ C_j $ manju and costs $ E_j $ yen. IOI Corporation will order some of these $ N $ types of boxes (between $ 0 $ and $ N $ types) and pack the manju into them for set sales. The price of each manju set is the sum of the prices of the manju included in it.

Assuming all manju sets are sold, what is the maximum profit IOI Corporation can achieve? Here, profit is defined as the total price of the sold manju sets minus the total price of the ordered boxes. Note that manju not packed into boxes will be enjoyed by IOI Corporation's staff, so they do not affect the profit.

Input Format

Read the following data from the standard input:

• The first line contains two integers $ M $ and $ N $ separated by a space, indicating there are $ M $ manju and $ N $ types of boxes.
• The next $ M $ lines contain an integer $ P_i $ each, indicating the price of the $ i $th manju is $ P_i $ yen.
• The next $ N $ lines contain two integers $ C_j $ and $ E_j $ separated by a space, indicating the $ j $th box can hold up to $ C_j $ manju and costs $ E_j $ yen.

Output Format

Output the maximum profit IOI Corporation can achieve in yen as a single integer on the standard output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

480

Sample Input #2

2 2
1000
2000
1 6666
1 7777

Sample Output #2

0

Sample Input #3

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

Sample Output #3

450

Notes/Hints

Task

Given the prices of each manju and the sizes and prices of each box, create a program to find the maximum profit IOI Corporation can achieve.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [25 points]

$N \leq 10$.

Subtask 2 [35 points]

$C_j \leq 10$ ($1 \leq j \leq N$).

Subtask 3 [40 points]

No additional constraints.

Sample Explanation 1

In this example, order the first box ($ 100 $ yen) and the second box ($ 120 $ yen). For instance, pack the first and second manju into the first box to sell as a set for $ 180 + 160 = 340 $ yen, and pack the third and fourth manju into the second box to sell as a set for $ 170 + 190 = 360 $ yen. The profit for IOI Corporation is $ 700 - 220 = 480 $ yen.

见题面 Input 部分

见题面 Output 部分