C - お買い物マラソン 解説 /

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

配点 : 366 点

問題文

高橋君は商店街で開催されている「お買い物マラソン」に参加しています。

商店街には N 軒のお店が左から右へ一列に並んでいます。各お店ではそれぞれ1種類の商品が売られており、左から i 番目のお店の商品の満足度は A_i 、価格は B_i です。

お買い物マラソンのルールは次の通りです。高橋君は商店街の中から 連続する区間 を1つ選び、その区間に含まれるすべてのお店で商品を1つずつ購入しなければなりません。具体的には、整数の組 (l, r)（ 1 \leq l \leq r \leq N ）を選び、左から l 番目から r 番目までのすべてのお店で買い物をします。

ただし、高橋君の所持金には限りがあり、選んだ区間のお店の価格の合計 B_l + B_{l+1} + \cdots + B_r が K 以下でなければなりません。

高橋君は、この条件を満たす区間の中で、満足度の合計 A_l + A_{l+1} + \cdots + A_r を最大化したいです。

なお、条件を満たす区間が1つも存在しない場合（すなわち、どの1軒のお店を選んでもその価格が K を超える場合）は、高橋君は何も購入できず、満足度の合計は 0 となります。

高橋君が得られる満足度の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{14}
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 入力はすべて整数である。

入力

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • 1 行目には、お店の数 N と所持金の上限 K が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（ 1 \leq i \leq N ）には、左から i 番目のお店の商品の満足度 A_i と価格 B_i が、スペース区切りで与えられる。

出力

高橋君が得られる満足度の合計の最大値を1行で出力してください。

入力例 1

5 10
3 2
5 3
2 4
8 1
1 5

出力例 1

18

入力例 2

3 2
5 3
8 4
3 7

出力例 2

0

入力例 3

10 15
4 3
7 2
1 5
9 1
3 4
6 2
2 7
8 3
5 1
10 6

出力例 3

26

入力例 4

20 50
12 3
8 7
15 2
6 9
20 4
3 8
11 1
7 5
14 6
9 3
5 10
18 2
4 7
16 4
2 6
13 3
10 8
1 5
19 2
7 4

出力例 4

108

入力例 5

1 1000000000000
1000000000 1

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi is participating in a "Shopping Marathon" held at a shopping street.

There are N shops lined up in a row from left to right in the shopping street. Each shop sells one type of product. The satisfaction of the product at the i-th shop from the left is A_i, and its price is B_i.

The rules of the Shopping Marathon are as follows. Takahashi must choose one contiguous interval from the shopping street and purchase exactly one product from every shop within that interval. Specifically, he chooses a pair of integers (l, r) (1 \leq l \leq r \leq N) and shops at every store from the l-th to the r-th from the left.

However, Takahashi's budget is limited, so the total price of the shops in the chosen interval B_l + B_{l+1} + \cdots + B_r must be at most K.

Takahashi wants to maximize the total satisfaction A_l + A_{l+1} + \cdots + A_r among all intervals satisfying this condition.

If no interval satisfies the condition (that is, if the price of every single shop exceeds K), Takahashi cannot purchase anything, and the total satisfaction is 0.

Find the maximum total satisfaction Takahashi can obtain.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{14}
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • All input values are integers.

Input

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N
  • The first line contains the number of shops N and the budget limit K, separated by a space.
  • The i-th of the following N lines (1 \leq i \leq N) contains the satisfaction A_i and price B_i of the product at the i-th shop from the left, separated by a space.

Output

Print the maximum total satisfaction Takahashi can obtain, in a single line.

Sample Input 1

5 10
3 2
5 3
2 4
8 1
1 5

Sample Output 1

18

Sample Input 2

3 2
5 3
8 4
3 7

Sample Output 2

0

Sample Input 3

10 15
4 3
7 2
1 5
9 1
3 4
6 2
2 7
8 3
5 1
10 6

Sample Output 3

26

Sample Input 4

20 50
12 3
8 7
15 2
6 9
20 4
3 8
11 1
7 5
14 6
9 3
5 10
18 2
4 7
16 4
2 6
13 3
10 8
1 5
19 2
7 4

Sample Output 4

108

Sample Input 5

1 1000000000000
1000000000 1

Sample Output 5

1000000000