After the apocalypse, it is time to build a new civilization led by Mr. Malnar. The first thing he will do is restore the tram network on the main street of his empire.

There are $n$ potential locations along the street, and Mr. Malnar will choose some of them to build tram stations. It has already been determined that there will be terminals at the first and $n$-th locations, so these locations must be chosen.

For each location, the values $x_i$ and $c_i$ are known, where $x_i$ represents the distance of that location from the beginning of the street, and $c_i$ represents the dissatisfaction of the residents if a station were at that location. Namely, some stations have kiosks whose vendors always overcharge for tickets, while others have excellent bakeries.

There are a total of $m$ residents who will use the planned line, so Mr. Malnar decided to ask each of them for their opinion. He learned that the $i$-th resident hates rides of length $d_i$ and evaluates the choice of stations as follows:

• The total satisfaction of that resident is equal to the sum of satisfaction for every pair of consecutive chosen stations.
• The satisfaction with two consecutive chosen stations that are at a distance $d$ is equal to $|d - d_i|$.

Mr. Malnar calculates the total satisfaction by summing the satisfaction of all $m$ residents and finally subtracting the dissatisfaction $c_k$ of all chosen stations $k$. Print the maximum satisfaction that Mr. Malnar can achieve with an optimal choice of stations.

Input

The first line contains natural numbers $n$ ($2 \le n \le 100\,000$) and $m$ ($1 \le m \le 100\,000$) from the problem text. The next line contains $m$ integers $d_i$ ($0 \le d_i \le 10^7$) from the problem text. The next $n$ lines describe the potential stations. Each station is described by its position $x_i$ ($0 \le x_i \le 10^7$) and dissatisfaction $c_i$ ($0 \le |c_i| \le 10^{12}$). The numbers $x_i$ and $c_i$ are integers, and additionally $x_1 < x_2 < \dots < x_n$.

Output

In a single line, print the maximum possible satisfaction.

Examples

Input 1

2 1
10
0 5
20 3

Output 1

2

Input 2

3 3
3 7 10
2 20
5 4
10 -3

Output 2

-1

Input 3

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

Output 3

137

Note

Explanation of the third example: It is optimal to choose stations 1, 3, 5, 7, and 9. The consecutive distances are then 6, 17, 49, and 25, and the residents' satisfactions are 61, 159, 89, 275, and 171, respectively. The sum of their satisfactions is 755, and the total dissatisfaction of the choice is 618, so the final result is 137.