C - 電波塔のカバー範囲 解説 /

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

配点 : 366 点

問題文

高橋君は直線状の道路沿いで、受信する信号の強度の合計が最大となる地点を探しています。

道路は数直線で表され、座標が増加する方向を右、減少する方向を左とします。道路上には N 基の電波塔が設置されており、塔 1, 塔 2, \ldots, 塔 N と番号が付けられています。塔 i は座標 X_i の位置に建っており、X_1 \leq X_2 \leq \cdots \leq X_N を満たします（同じ座標に複数の塔が建っていることもあります）。

塔 i の電波は、塔の位置から左方向に距離 L_i、右方向に距離 R_i だけ届きます。すなわち、座標 X_i - L_i 以上 X_i + R_i 以下の範囲をカバーします。塔 i のカバー範囲内にいるとき、受信できる信号の強度は C_i です。

高橋君は道路上の任意の整数座標の地点を 1 つ選んで立ちます（負の座標も選べます）。高橋君が座標 p（整数）に立ったとき、受信できる信号の強度の合計は

\displaystyle\sum_{\substack{1 \leq i \leq N \\ X_i - L_i \leq p \leq X_i + R_i}} C_i

です。すなわち、p がカバー範囲に含まれるすべての塔の信号の強度の和です。どの塔のカバー範囲にも含まれない地点を選んだ場合、信号の強度の合計は 0 です。

高橋君が立つ地点を最適に選んだとき、受信できる信号の強度の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 0 \leq X_i \leq 10^9
  • X_1 \leq X_2 \leq \cdots \leq X_N
  • 0 \leq L_i \leq 10^9
  • 0 \leq R_i \leq 10^9
  • 1 \leq C_i \leq 10^4
  • 入力はすべて整数である。

入力

N
X_1 L_1 R_1 C_1
X_2 L_2 R_2 C_2
\vdots
X_N L_N R_N C_N

1 行目には、電波塔の数を表す整数 N が与えられる。続く N 行のうち i 行目 (1 \leq i \leq N) には、塔 i の座標 X_i、電波が左に届く距離 L_i、電波が右に届く距離 R_i、信号の強度 C_i が、スペース区切りで与えられる。

出力

高橋君が受信できる信号の強度の合計の最大値を整数として 1 行で出力せよ。

入力例 1

3
2 1 2 5
5 2 0 4
6 1 1 3

出力例 1

9

入力例 2

4
0 0 0 7
0 1 2 3
3 1 0 5
10 0 0 1

出力例 2

10

入力例 3

8
1 1 0 2
4 2 3 5
6 0 2 4
8 3 1 6
10 5 0 3
10 0 4 7
13 2 2 1
20 10 0 8

出力例 3

18

入力例 4

15
0 0 5 2
2 1 2 4
4 3 0 6
7 2 5 3
9 0 0 8
12 4 1 5
15 5 5 7
18 3 2 4
18 0 6 9
23 10 0 1
25 2 3 6
30 8 4 5
35 0 0 10
40 7 7 2
50 20 0 8

出力例 4

21

入力例 5

1
1000000000 1000000000 1000000000 10000

出力例 5

10000

Score : 366 pts

Problem Statement

Takahashi is searching for a point along a straight road where the total strength of received signals is maximized.

The road is represented by a number line, where the direction of increasing coordinates is called right and the direction of decreasing coordinates is called left. There are N radio towers installed along the road, numbered Tower 1, Tower 2, \ldots, Tower N. Tower i is built at coordinate X_i, satisfying X_1 \leq X_2 \leq \cdots \leq X_N (multiple towers may be built at the same coordinate).

The radio waves from Tower i reach a distance of L_i to the left and R_i to the right from the tower's position. That is, it covers the range from coordinate X_i - L_i to coordinate X_i + R_i, inclusive. When within the coverage area of Tower i, the strength of the signal that can be received is C_i.

Takahashi will choose and stand at any single point on the road with an integer coordinate (negative coordinates are also allowed). When Takahashi stands at coordinate p (an integer), the total strength of the signals he can receive is

\displaystyle\sum_{\substack{1 \leq i \leq N \\ X_i - L_i \leq p \leq X_i + R_i}} C_i

That is, it is the sum of signal strengths of all towers whose coverage area includes p. If the chosen point is not within the coverage area of any tower, the total signal strength is 0.

Find the maximum total signal strength Takahashi can receive when he optimally chooses where to stand.

Constraints

  • 1 \leq N \leq 10^5
  • 0 \leq X_i \leq 10^9
  • X_1 \leq X_2 \leq \cdots \leq X_N
  • 0 \leq L_i \leq 10^9
  • 0 \leq R_i \leq 10^9
  • 1 \leq C_i \leq 10^4
  • All inputs are integers.

Input

N
X_1 L_1 R_1 C_1
X_2 L_2 R_2 C_2
\vdots
X_N L_N R_N C_N

The first line contains an integer N representing the number of radio towers. The i-th of the following N lines (1 \leq i \leq N) contains the coordinate X_i of Tower i, the distance L_i the radio waves reach to the left, the distance R_i the radio waves reach to the right, and the signal strength C_i, separated by spaces.

Output

Output the maximum total signal strength that Takahashi can receive, as an integer on a single line.

Sample Input 1

3
2 1 2 5
5 2 0 4
6 1 1 3

Sample Output 1

9

Sample Input 2

4
0 0 0 7
0 1 2 3
3 1 0 5
10 0 0 1

Sample Output 2

10

Sample Input 3

8
1 1 0 2
4 2 3 5
6 0 2 4
8 3 1 6
10 5 0 3
10 0 4 7
13 2 2 1
20 10 0 8

Sample Output 3

18

Sample Input 4

15
0 0 5 2
2 1 2 4
4 3 0 6
7 2 5 3
9 0 0 8
12 4 1 5
15 5 5 7
18 3 2 4
18 0 6 9
23 10 0 1
25 2 3 6
30 8 4 5
35 0 0 10
40 7 7 2
50 20 0 8

Sample Output 4

21

Sample Input 5

1
1000000000 1000000000 1000000000 10000

Sample Output 5

10000