C - 本棚の整理 解説 /

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

配点 : 366 点

問題文

高橋君は自宅の本棚を整理しています。本棚には N 冊の本が一列に並んでおり、左から順に 1, 2, \ldots, N の番号が付けられています。本 i の満足度は A_i 、重さは B_i です。

高橋君は、本棚から 1冊以上の連続する本 を選んで取り出し、新しい棚に移動させようとしています。具体的には、整数 l, r （ 1 \leq l \leq r \leq N ）を選び、本 l, l+1, \ldots, r をすべて取り出します。

ただし、高橋君が一度に運べる重さには限界があり、選んだ区間に含まれる本の重さの合計が K 以下でなければなりません。すなわち、

B_l + B_{l+1} + \cdots + B_r \leq K

を満たす必要があります。

この条件を満たすような l, r の選び方のうち、満足度の合計 A_l + A_{l+1} + \cdots + A_r が最大となる値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{15}
  • 1 \leq A_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq B_i \leq 10^9 （ 1 \leq i \leq N ）
  • 入力はすべて整数である
  • 重さの合計が K 以下となる区間 (l, r)（ 1 \leq l \leq r \leq N ）が少なくとも1つ存在する

入力

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • 1 行目には、本の冊数を表す整数 N と、重さの上限を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各本の満足度を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各本の重さを表す整数 B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。

出力

重さの合計が K 以下となる連続区間を選んだときの、満足度の合計の最大値を 1 行で出力せよ。

入力例 1

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

出力例 1

15

入力例 2

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

出力例 2

25

入力例 3

10 1000000000000000
100 200 300 400 500 600 700 800 900 1000
1 1 1 1 1 1 1 1 1 1

出力例 3

5500

Score : 366 pts

Problem Statement

Takahashi is organizing the bookshelf in his house. The bookshelf contains N books arranged in a row, numbered 1, 2, \ldots, N from left to right. Book i has a satisfaction value of A_i and a weight of B_i.

Takahashi wants to select one or more consecutive books from the bookshelf and move them to a new shelf. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N) and takes out all books l, l+1, \ldots, r.

However, there is a limit to the weight Takahashi can carry at once, so the total weight of the books in the selected interval must be at most K. That is, the following condition must be satisfied:

B_l + B_{l+1} + \cdots + B_r \leq K

Among all choices of l, r that satisfy this condition, find the maximum value of the total satisfaction A_l + A_{l+1} + \cdots + A_r.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{15}
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers
  • There exists at least one interval (l, r) (1 \leq l \leq r \leq N) such that the total weight is at most K

Input

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
  • The first line contains an integer N representing the number of books and an integer K representing the weight limit, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the satisfaction values of each book, separated by spaces.
  • The third line contains integers B_1, B_2, \ldots, B_N representing the weights of each book, separated by spaces.

Output

Print in one line the maximum total satisfaction when selecting a contiguous interval whose total weight is at most K.

Sample Input 1

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

Sample Output 1

15

Sample Input 2

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

Sample Output 2

25

Sample Input 3

10 1000000000000000
100 200 300 400 500 600 700 800 900 1000
1 1 1 1 1 1 1 1 1 1

Sample Output 3

5500