E - 電波塔と信号強度 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は通信会社のエンジニアとして、道路沿いの電波状況の調査を担当しています。

調査対象の道路は一直線で、道路沿いには N 基の電波塔が建てられています。道路は数直線として表され、 i 番目の電波塔は座標 X_i に建てられており、出力 B_i を持っています。

座標 p における「信号強度」は、すべての電波塔からの寄与の合計として次のように定義されます。

f(p) = \sum_{i=1}^{N} \max(0,\ B_i - |p - X_i|)

すなわち、各電波塔 i は座標 p に対して \max(0,\ B_i - |p - X_i|) だけの信号強度を届けます。電波塔から離れるほど信号は弱くなり、距離が出力 B_i 以上になると届かなくなります。

高橋君の同僚である青木君は、 Q 個の区間について信号強度の調査を行います。各調査 j では区間 [L_j, R_j] が与えられるので、その区間内の整数座標における f(p) の最大値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 0 \leq X_i \leq 2 \times 10^5
  • 1 \leq B_i \leq 2 \times 10^5
  • 0 \leq L_j \leq R_j \leq 2 \times 10^5
  • 入力はすべて整数である。

入力

N Q
X_1 B_1
X_2 B_2
:
X_N B_N
L_1 R_1
L_2 R_2
:
L_Q R_Q
  • 1 行目には、電波塔の数を表す N と、調査の数を表す Q が、スペース区切りで与えられる。
  • 2 行目から N 行では、各電波塔の情報が与えられる。
  • 1 + i 行目では、 i 番目の電波塔の座標 X_i と出力 B_i が、スペース区切りで与えられる。
  • 続く Q 行では、各調査の情報が与えられる。
  • 1 + N + j 行目では、 j 番目の調査の区間の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

Q 行出力せよ。 j 行目には、 j 番目の調査に対する答え、すなわち区間 [L_j, R_j] 内の整数座標における f(p) の最大値を出力せよ。

入力例 1

1 2
5 3
0 10
0 3

出力例 1

3
1

入力例 2

3 3
2 3
5 4
10 2
0 10
6 10
9 12

出力例 2

4
3
2

入力例 3

5 5
0 5
10 3
20 8
15 6
25 4
0 30
12 18
0 5
20 25
0 0

出力例 3

9
9
5
9
5

Score : 466 pts

Problem Statement

Takahashi is an engineer at a telecommunications company, responsible for investigating radio conditions along a road.

The road under investigation is a straight line, and N radio towers are built along the road. The road is represented as a number line, where the i-th radio tower is located at coordinate X_i and has power output B_i.

The "signal strength" at coordinate p is defined as the sum of contributions from all radio towers:

f(p) = \sum_{i=1}^{N} \max(0,\ B_i - |p - X_i|)

That is, each radio tower i delivers a signal strength of \max(0,\ B_i - |p - X_i|) to coordinate p. The signal weakens as one moves farther from the tower, and it no longer reaches once the distance is at least B_i.

Takahashi's colleague Aoki will conduct signal strength surveys for Q intervals. For each survey j, an interval [L_j, R_j] is given. Find the maximum value of f(p) over all integer coordinates p within that interval.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 0 \leq X_i \leq 2 \times 10^5
  • 1 \leq B_i \leq 2 \times 10^5
  • 0 \leq L_j \leq R_j \leq 2 \times 10^5
  • All input values are integers.

Input

N Q
X_1 B_1
X_2 B_2
:
X_N B_N
L_1 R_1
L_2 R_2
:
L_Q R_Q
  • The first line contains N, the number of radio towers, and Q, the number of surveys, separated by a space.
  • The following N lines give information about each radio tower.
  • The (1 + i)-th line contains the coordinate X_i and the power output B_i of the i-th radio tower, separated by a space.
  • The following Q lines give information about each survey.
  • The (1 + N + j)-th line contains the left endpoint L_j and the right endpoint R_j of the interval for the j-th survey, separated by a space.

Output

Output Q lines. The j-th line should contain the answer to the j-th survey, that is, the maximum value of f(p) over all integer coordinates p within the interval [L_j, R_j].

Sample Input 1

1 2
5 3
0 10
0 3

Sample Output 1

3
1

Sample Input 2

3 3
2 3
5 4
10 2
0 10
6 10
9 12

Sample Output 2

4
3
2

Sample Input 3

5 5
0 5
10 3
20 8
15 6
25 4
0 30
12 18
0 5
20 25
0 0

Sample Output 3

9
9
5
9
5