分数: 366 分
问题陈述
Takahashi 是一家电信公司的工程师。他被分配了一个铺设新光纤电缆的项目。
有 N 沿道路设有中继站,每个站都排成一条直线。车站已编号 1, 2, \ldots, N 按照与道路起点的距离递增的顺序,并且 i第站位于 距起点 X_i 米 (X_1 < X_2 < \cdots < X_N)。激活每个站 i 成本 C_i 一万日元。
高桥的项目已分配预算 M 一万日元。为了铺设光缆,高桥可以选择一个连续的站点间隔。具体来说,他选择一对整数 (l, r) 满意 1 \leq l \leq r \leq N,并激活来自 l-第 r-th。所需成本是所选时间间隔内所有站点的总激活成本, \displaystyle\sum_{i=l}^{r} C_i 一万日元,不得超过预算 M 一万日元。请注意,站点之间铺设电缆的成本可以忽略不计。
当有效 在此条件下选择 (l, r) ,光纤电缆 X_r - X_l 米可以铺设(如果 l = r,长度为 0 米)。如果没有符合预算的区间,或者高桥选择不选择任何区间,则不铺设任何东西,电缆长度为 0 米。
找出 Takahashi 可以铺设的光缆的最大长度(以米为单位)。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^{14}
- 1 \leq X_i \leq 10^9 (1 \leq i \leq N)
- X_1 < X_2 < \cdots < X_N
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N M X_1 C_1 X_2 C_2 \vdots X_N C_N
- 第一行包含一个整数 N 代表站数和一个整数 M 代表预算(单位:万日元),以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个车站的信息。
- 的 树的 (1 + i)- 第行包含一个整数 X_i 代表位置(以米为单位) i第一个站和一个整数 C_i 代表激活该站所需的费用(万日元),以空格分隔。
- 站点按位置升序给出,并保证 X_1 < X_2 < \cdots < X_N.
输出
打印高桥可以在单线上铺设的光缆的最大长度(以米为单位)。
示例输入 1
5 10 1 2 3 3 7 4 12 5 20 6
示例输出 1
6
示例输入 2
4 5 10 3 20 3 30 3 40 3
示例输出 2
0
示例输入 3
8 100 5 10 15 20 30 15 50 25 80 30 120 10 200 40 300 50
示例输出 3
180