IOI Manju

Interview

Time limit1sMemory limit256 MB

Summary

Choose boxes and fill them with the priciest manju so packed value minus box cost is as large as possible.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Prefix sum
Solved: No attempts yet

Problem

IOI Inc. made $M$ distinct IOI manju. Manju $i$ costs $P_i$ yen ( $1 \le i \le M$ ).

JOI Inc. offers $N$ box types. Box $j$ ( $1 \le j \le N$ ) holds up to $C_j$ manju and costs $E_j$ yen. IOI orders between 0 and $N$ box types, one of each chosen type, packs manju into them, and sells each packed set for the sum of manju prices inside.

If every set sells, what is the maximum profit (total manju sales minus total box costs)? Manju left unpacked do not affect profit.

Input

Line 1: $M$ , $N$ .
Next $M$ lines: $P_i$ .
Next $N$ lines: $C_j$ , $E_j$ .

Output

One integer: maximum profit.

Constraints

$1 \le M \le 10\,000$ .
$1 \le N \le 500$ .
$1 \le P_i \le 10\,000$ .
$1 \le C_j \le 10\,000$ .
$1 \le E_j \le 10\,000$ .

Examples5

Example 1

Input

Expected output

Example 2
Input
```
2 2
1000
2000
1 6666
1 7777
```
Expected output
```
0
```

Example 3

Input

Expected output

Example 4

Input

Expected output

Example 5

Input

Expected output