← 返回题目列表

AtCoder · awc0104_d

D. 无线电塔和接收器

中文机器翻译题面 查看原题

分数: 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