C - Laying Optical Fiber Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は通信会社のエンジニアです。新しい光ファイバー回線を敷設するプロジェクトを任されました。

道路沿いに N 個の中継基地があり、各基地は一直線上に並んでいます。基地には道路の起点から近い順に 1, 2, \ldots, N と番号が付けられており、i 番目の基地は道路の起点から X_i メートルの位置にあります（X_1 < X_2 < \cdots < X_N）。各基地 i を稼働させるためには C_i 万円の費用がかかります。

高橋君のプロジェクトには M 万円の予算が割り当てられています。光ファイバー回線を敷設するために、高橋君は連続する基地の区間を1つ選ぶことができます。具体的には、1 \leq l \leq r \leq N を満たす整数の組 (l, r) を1つ選び、l 番目から r 番目までのすべての基地を稼働させます。このとき必要な費用は、選んだ区間に含まれる基地の稼働費用の合計 \displaystyle\sum_{i=l}^{r} C_i 万円であり、これが予算 M 万円以下でなければなりません。なお、基地間のケーブル敷設にかかる費用は考えなくてよいものとします。

この条件を満たす (l, r) を選んだとき、X_r - X_l メートルの光ファイバー回線を敷設できます（l = r の場合は 0 メートルです）。高橋君は、予算内で選べる区間がない場合や、あえて区間を選ばない場合には何も敷設しないこともでき、その場合の回線の長さは 0 メートルです。

高橋君が敷設できる光ファイバー回線の長さの最大値をメートル単位で求めてください。

制約

  • 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
  • 1 行目には、基地の数を表す整数 N と、予算（万円）を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目には、各基地の情報が与えられる。
  • 1 + i 行目には、i 番目の基地の位置（メートル）を表す整数 X_i と、その基地を稼働させるために必要な費用（万円）を表す整数 C_i が、スペース区切りで与えられる。
  • 基地は位置の昇順に並んでおり、X_1 < X_2 < \cdots < X_N が保証される。

出力

高橋君が敷設できる光ファイバー回線の長さの最大値をメートル単位で 1 行に出力せよ。

入力例 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

Score : 366 pts

Problem Statement

Takahashi is an engineer at a telecommunications company. He has been assigned a project to lay new fiber optic cables.

There are N relay stations along a road, and each station is aligned in a straight line. The stations are numbered 1, 2, \ldots, N in order of increasing distance from the starting point of the road, and the i-th station is located X_i meters from the starting point (X_1 < X_2 < \cdots < X_N). Activating each station i costs C_i ten-thousand yen.

Takahashi's project has been allocated a budget of M ten-thousand yen. To lay the fiber optic cable, Takahashi can select one contiguous interval of stations. Specifically, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and activates all stations from the l-th to the r-th. The required cost is the total activation cost of all stations in the chosen interval, \displaystyle\sum_{i=l}^{r} C_i ten-thousand yen, which must not exceed the budget of M ten-thousand yen. Note that the cost of laying cables between stations can be ignored.

When a valid (l, r) is chosen under this condition, a fiber optic cable of X_r - X_l meters can be laid (if l = r, the length is 0 meters). If there is no interval that fits within the budget, or if Takahashi chooses not to select any interval, nothing is laid, and the cable length is 0 meters.

Find the maximum length of fiber optic cable that Takahashi can lay, in meters.

Constraints

  • 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)
  • All inputs are integers

Input

N M
X_1 C_1
X_2 C_2
\vdots
X_N C_N
  • The first line contains an integer N representing the number of stations and an integer M representing the budget (in ten-thousand yen), separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each station is given.
  • The (1 + i)-th line contains an integer X_i representing the position (in meters) of the i-th station and an integer C_i representing the cost (in ten-thousand yen) required to activate that station, separated by a space.
  • The stations are given in ascending order of position, and it is guaranteed that X_1 < X_2 < \cdots < X_N.

Output

Print the maximum length of fiber optic cable that Takahashi can lay, in meters, on a single line.

Sample Input 1

5 10
1 2
3 3
7 4
12 5
20 6

Sample Output 1

6

Sample Input 2

4 5
10 3
20 3
30 3
40 3

Sample Output 2

0

Sample Input 3

8 100
5 10
15 20
30 15
50 25
80 30
120 10
200 40
300 50

Sample Output 3

180