分数: 400 分
问题陈述
Takahashi 正尝试在其中一个位置安装接收器 N 点排列成一条直线。点已编号 1, 2, \ldots, N 从左到右,以及点的坐标 i is i (即相邻点之间的距离为 1).
有 M 无线电塔建在这条线上。的 j第无线电塔 (1 \leq j \leq M) 位于点 P_j 并用功率发射无线电波 B_j。请注意,同一点可能存在多个无线电塔。
来自的“接收强度” j- 点处的无线电塔 i 定义为 B_j - |i - P_j|。来自该塔的无线电波被认为到达了点 i 仅当接收强度为正时(即, B_j - |i - P_j| > 0).
“总接收强度” S_i 在点 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 if S_i \leq T_i。如果 S_i > T_i,由于信号过载,接收器无法正常工作。
Takahashi 希望将接收器安装在接收器正常运行的点(即满足 S_i \leq T_i)以及哪里 S_i 已最大化。
保证至少存在一个接收器正常工作的点。找到最大值 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)
- 至少存在一个接收器正常运行的点。
- 所有输入值均为整数。
输入
N M T_1 T_2 \ldots T_N P_1 B_1 P_2 B_2 \vdots P_M B_M
- 第一行包含点数 N 和无线电塔的数量 M,用空格分隔。
- 第二行包含公差值 每个点的 T_1, T_2, \ldots, T_N ,用空格分隔。
- 在下面 M 行, j第行 (1 \leq j \leq M) 包含位置 P_j 和电源 B_j 的 j第一个无线电塔,间隔一个空格。
输出
打印最大值 S_i 在接收器正常运行的点之间,在一条线上。
示例输入 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