分数: 366 分
问题陈述
Takahashi 正在沿着直路寻找接收信号总强度最大的点。
道路用数轴表示,坐标增加的方向称为右,坐标减少的方向称为左。有 N 沿路安装的无线电塔,编号为Tower 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.
高桥会选择并站在道路上具有整数坐标的任意单个点(也允许负坐标)。当高桥站在坐标上时 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
第一行包含一个整数 N 代表无线电塔的数量。的 i- 以下各项 N 行 (1 \leq i \leq N) 包含坐标 塔的 X_i 塔的 i,距离 L_i 无线电波到达左边,距离 R_i 无线电波到达右侧,信号强度 C_i,用空格分隔。
输出
以单行整数形式输出高桥可以接收的最大总信号强度。
示例输入 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