/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、一直線上に並んだ N 個の地点のいずれかに受信機を設置しようとしています。地点は左から順に 1, 2, \ldots, N と番号が付けられており、地点 i の座標は i です（すなわち、隣接する地点間の距離は 1 です）。
この直線上には M 基の電波塔が建っており、j 番目の電波塔 (1 \leq j \leq M) は地点 P_j に位置し、出力 B_j の電波を発信しています。なお、同じ地点に複数の電波塔が存在することもあります。
地点 i における j 番目の電波塔からの「受信強度」は B_j - |i - P_j| と定義されます。受信強度が正（すなわち B_j - |i - P_j| > 0）である場合にのみ、その電波塔からの電波は地点 i に届くものとみなします。
地点 i における「受信強度の合計」S_i を、電波が届くすべての電波塔についての受信強度の総和として定義します。すなわち、
S_i = \sum_{\substack{1 \leq j \leq M \\ B_j - |i - P_j| > 0}} (B_j - |i - P_j|)
です。どの電波塔からも電波が届かない場合は S_i = 0 とします。
各地点 i には「許容値」T_i が設定されています。地点 i において S_i \leq T_i であるとき、その地点で受信機は正常に動作します。S_i > T_i であるとき、受信機は電波の過負荷により正常に動作しません。
高橋君は、受信機が正常に動作する地点（すなわち S_i \leq T_i を満たす地点）の中から、S_i が最大となる地点を選んで受信機を設置したいと考えています。
受信機が正常に動作する地点が少なくとも 1 つ存在することが保証されます。そのような地点における S_i の最大値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq T_i \leq 10^{14} (1 \leq i \leq N)
- 1 \leq P_j \leq N (1 \leq j \leq M)
- 1 \leq B_j \leq N (1 \leq j \leq M)
- 受信機が正常に動作する地点が少なくとも 1 つ存在する。
- 入力はすべて整数である。
入力
N M T_1 T_2 \ldots T_N P_1 B_1 P_2 B_2 \vdots P_M B_M
- 1 行目には、地点の数 N と電波塔の数 M が、スペース区切りで与えられる。
- 2 行目には、各地点の許容値 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
- 続く M 行のうち j 行目 (1 \leq j \leq M) には、j 番目の電波塔の位置 P_j と出力 B_j が、スペース区切りで与えられる。
出力
受信機が正常に動作する地点における S_i の最大値を 1 行で出力せよ。
入力例 1
5 1 2 5 2 3 1 3 3
出力例 1
2
入力例 2
10 3 5 2 10 3 3 4 3 5 1 1 2 3 7 4 5 2
出力例 2
4
入力例 3
15 4 10 8 6 5 4 3 5 7 8 10 5 3 2 3 4 3 5 10 6 8 3 15 4
出力例 3
7
Score : 400 pts
Problem Statement
Takahashi is trying to install a receiver at one of N points arranged in a straight line. The points are numbered 1, 2, \ldots, N from left to right, and the coordinate of point i is i (that is, the distance between adjacent points is 1).
There are M radio towers built on this line. The j-th radio tower (1 \leq j \leq M) is located at point P_j and transmits radio waves with power B_j. Note that multiple radio towers may exist at the same point.
The "reception strength" from the j-th radio tower at point i is defined as B_j - |i - P_j|. The radio waves from that tower are considered to reach point i only if the reception strength is positive (i.e., B_j - |i - P_j| > 0).
The "total reception strength" S_i at point i is defined as the sum of reception strengths over all radio towers whose waves reach that point. That is,
S_i = \sum_{\substack{1 \leq j \leq M \\ B_j - |i - P_j| > 0}} (B_j - |i - P_j|)
If no radio waves from any tower reach the point, then S_i = 0.
Each point i has a "tolerance value" T_i. The receiver operates normally at point i if S_i \leq T_i. If S_i > T_i, the receiver does not operate normally due to signal overload.
Takahashi wants to install the receiver at a point where the receiver operates normally (i.e., a point satisfying S_i \leq T_i) and where S_i is maximized.
It is guaranteed that there exists at least one point where the receiver operates normally. Find the maximum value of S_i among such points.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq T_i \leq 10^{14} (1 \leq i \leq N)
- 1 \leq P_j \leq N (1 \leq j \leq M)
- 1 \leq B_j \leq N (1 \leq j \leq M)
- There exists at least one point where the receiver operates normally.
- All input values are integers.
Input
N M T_1 T_2 \ldots T_N P_1 B_1 P_2 B_2 \vdots P_M B_M
- The first line contains the number of points N and the number of radio towers M, separated by a space.
- The second line contains the tolerance values T_1, T_2, \ldots, T_N for each point, separated by spaces.
- In the following M lines, the j-th line (1 \leq j \leq M) contains the position P_j and power B_j of the j-th radio tower, separated by a space.
Output
Print the maximum value of S_i among points where the receiver operates normally, in a single line.
Sample Input 1
5 1 2 5 2 3 1 3 3
Sample Output 1
2
Sample Input 2
10 3 5 2 10 3 3 4 3 5 1 1 2 3 7 4 5 2
Sample Output 2
4
Sample Input 3
15 4 10 8 6 5 4 3 5 7 8 10 5 3 2 3 4 3 5 10 6 8 3 15 4
Sample Output 3
7