Imperial Civilization

Time limit1.5sMemory limit512 MB

Summary

Choose a subset of stops that must include the first and last positions to maximize total resident satisfaction minus stop dissatisfaction, where each consecutive gap of length d scores the sum of |d - d_i|.

Level: Hard9 of 10
Topics: Dynamic programming, Divide and conquer, Geometry
Solved: No attempts yet

Problem

After the apocalypse, Mr. Malnar sets out to build a new civilization. His first project is to rebuild the tram network on the main street of his empire.

There are $n$ candidate positions along the street, and Mr. Malnar picks some of them for tram stops. The first and the $n$ -th positions are turnaround stops, so both must be chosen.

Each position $i$ has a distance $x_i$ from the start of the street and a dissatisfaction $c_i$ that residents feel if a stop is built there. Some stops have kiosks that always overcharge for tickets, and some have excellent bakeries.

There are $m$ residents who will use the line. Resident $i$ dislikes rides of length $d_i$ and rates a chosen set of stops as follows:

The total satisfaction of this resident is the sum of satisfaction over every pair of consecutive chosen stops.
Two consecutive chosen stops at distance $d$ give satisfaction $|d - d_i|$ .

Mr. Malnar adds up the satisfaction of all $m$ residents, then subtracts the dissatisfaction $c_k$ of every chosen stop $k$ . Find the maximum total he can achieve by choosing the stops optimally.

Input

The first line contains the natural numbers $n$ ( $2 \le n \le 100\,000$ ) and $m$ ( $1 \le m \le 100\,000$ ).

The second line contains $m$ integers $d_i$ ( $0 \le d_i \le 10^7$ ).

The next $n$ lines describe the candidate positions. Each line contains the position $x_i$ ( $0 \le x_i \le 10^7$ ) and the dissatisfaction $c_i$ ( $0 \le |c_i| \le 10^{12}$ ). All $x_i$ and $c_i$ are integers, and $x_1 < x_2 < \ldots < x_n$ .

Output

Print one line with the maximum possible total satisfaction.

Hint

Note on the third sample: The optimal choice is positions 1, 3, 5, 7, and 9. The consecutive distances are 6, 17, 49, and 25, and the residents' satisfaction values are 61, 159, 89, 275, and 171 in that order. The satisfaction values sum to 755, and the chosen stops have a total dissatisfaction of 618, so the final result is 137.

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