Pumpkin Placement

Time limit2sMemory limit1024 MB

Summary

Pick fence positions, always including the first and last, to maximize total gap satisfaction minus the chosen discontentment costs.

Level: Hard8 of 10
Topics: Dynamic programming, Divide and conquer, Sorting, Prefix sum
Solved: No attempts yet

Problem

For Halloween, $m$ residents decided to place a number of pumpkins along the fence of their house. In advance, $n$ candidate positions were chosen. Position $i$ has two parameters: $x_i$ , its distance from the start of the fence, and $c_i$ , the discontentment level of the residents if a pumpkin is placed there. Regardless of anything else, pumpkins are definitely placed at position $1$ and position $n$ .

Each resident $i$ named a favorite number $d_i$ . For resident $i$ , the satisfaction from two adjacent pumpkins at distance $d$ apart is $|d - d_i|$ . The total satisfaction of a resident is the sum of these values over every pair of adjacent pumpkins.

If pumpkins are placed at positions $j_1, j_2, \ldots, j_k$ (in order along the fence), the total satisfaction is computed as $\left(\sum_{i=1}^{m} \sum_{t=2}^{k} |x_{j_t} - x_{j_{t-1}} - d_i|\right) - \left(\sum_{t=1}^{k} c_{j_t}\right)$ .

The residents want to maximize this total satisfaction by choosing the positions for the pumpkins optimally.

Input

The first line contains two integers $n$ and $m$ , the number of candidate positions and the number of residents ( $2 \leq n \leq 10^5$ , $1 \leq m \leq 10^5$ ).

The second line contains $m$ integers $d_i$ , the favorite number of each resident ( $0 \leq d_i \leq 10^7$ ).

Each of the next $n$ lines contains two integers $x_i$ and $c_i$ , the parameters of a candidate position ( $0 \leq x_i \leq 10^7$ , $0 \leq |c_i| \leq 10^{12}$ ). It is guaranteed that $x_1 < x_2 < \ldots < x_n$ .

Output

Print one integer, the maximum total satisfaction of the residents.

Examples3

Example 1
Input
```
2 1
10
0 5
20 3
```
Expected output
```
2
```
Example 2
Input
```
3 3
3 7 10
2 20
5 4
10 -3
```
Expected output
```
-1
```

Example 3

Input

9 5
30 64 2 93 67
0 81
1 256
6 251
13 256
23 180
52 256
72 94
77 256
97 12

Expected output