← 返回题目列表

AtCoder · awc0083_c

C. 铺设光纤

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

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