/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君の住む町には、一直線に並んだ N 地点の桜スポットがあり、順にスポット 1, スポット 2, \ldots, スポット N と番号が付けられています。隣り合うスポット同士はそれぞれ遊歩道で結ばれており、スポット i とスポット i + 1 を結ぶ遊歩道 i（1 \leq i \leq N - 1）が存在します。遊歩道は合計 N - 1 本です。
各スポット j（1 \leq j \leq N）には、その地点の桜の美しさを表すスコア P_j が定められています。また、各遊歩道 i（1 \leq i \leq N - 1）には整備コスト C_i が設定されています。
高橋君は、連続する区間の遊歩道をまとめて整備し、散歩コースを作ろうと考えています。具体的には、整数 l, r（1 \leq l \leq r \leq N - 1）を選び、遊歩道 l, 遊歩道 l+1, \ldots, 遊歩道 r をすべて整備します。このとき、整備された遊歩道沿いにあるスポット l, スポット l+1, \ldots, スポット r+1 の すべて を散歩コースとして訪れることができます。
散歩コースから得られる 満足度 は、コースに含まれる r - l + 2 個のスポットのスコアの合計
P_l + P_{l+1} + \cdots + P_{r+1}
と定義されます。
一方、整備にかかる 総コスト は
C_l + C_{l+1} + \cdots + C_r
です。
高橋君の予算は B であり、総コストが B 以下となるような (l, r) のみ選択できます。高橋君は必ずいずれかの区間を選んで整備を行います。
総コストが B 以下であるようなすべての (l, r) の選び方の中で、満足度の最大値 を求めてください。
なお、制約より各遊歩道の整備コストは B 以下であるため、l = r（遊歩道を 1 本だけ整備する場合）は必ず条件を満たし、選択可能な (l, r) は 1 つ以上存在します。
制約
- 2 \leq N \leq 5 \times 10^5
- 1 \leq B \leq 10^{14}
- 1 \leq P_j \leq 10^9（1 \leq j \leq N）
- 1 \leq C_i \leq B（1 \leq i \leq N - 1）
- 入力はすべて整数である
入力
N B
P_1 P_2 \ldots P_N
C_1 C_2 \ldots C_{N-1}
- 1 行目には、桜スポットの数を表す整数 N と、予算を表す整数 B が、スペース区切りで与えられる。
- 2 行目には、各スポットのスコアを表す N 個の整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
- 3 行目には、各遊歩道の整備コストを表す N - 1 個の整数 C_1, C_2, \ldots, C_{N-1} が、スペース区切りで与えられる。
出力
総コストが B 以下となる整備区間における満足度の最大値を 1 行で出力せよ。
入力例 1
5 10 3 1 4 1 5 2 3 4 5
出力例 1
10
入力例 2
4 3 10 20 30 40 1 2 3
出力例 2
70
入力例 3
10 15 5 8 3 10 7 2 9 6 4 11 3 2 5 1 4 6 2 3 7
出力例 3
35
入力例 4
20 50 12 5 18 3 15 9 20 7 14 6 11 8 19 2 16 10 4 13 17 1 3 7 2 8 1 5 4 6 9 3 7 2 8 1 5 4 6 9 3
出力例 4
130
入力例 5
2 100000000000000 1000000000 1000000000 1
出力例 5
2000000000
Score : 366 pts
Problem Statement
In the town where Takahashi lives, there are N cherry blossom spots arranged in a straight line, numbered Spot 1, Spot 2, \ldots, Spot N in order. Adjacent spots are connected by promenades, and there exists promenade i (1 \leq i \leq N - 1) connecting Spot i and Spot i + 1. There are N - 1 promenades in total.
Each Spot j (1 \leq j \leq N) has a score P_j representing the beauty of the cherry blossoms at that location. Additionally, each promenade i (1 \leq i \leq N - 1) has a maintenance cost C_i.
Takahashi plans to maintain a contiguous interval of promenades to create a walking course. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N - 1) and maintains all of promenade l, promenade l+1, \ldots, promenade r. By doing so, he can visit all of Spot l, Spot l+1, \ldots, Spot r+1 along the maintained promenades as his walking course.
The satisfaction obtained from the walking course is defined as the sum of the scores of the r - l + 2 spots included in the course:
P_l + P_{l+1} + \cdots + P_{r+1}
On the other hand, the total cost of maintenance is:
C_l + C_{l+1} + \cdots + C_r
Takahashi's budget is B, and he can only choose (l, r) such that the total cost is at most B. Takahashi must choose and maintain exactly one such interval.
Among all ways to choose (l, r) such that the total cost is at most B, find the maximum value of the satisfaction.
Note that, due to the constraints, the maintenance cost of each promenade is at most B, so l = r (maintaining just one promenade) always satisfies the condition, and there exists at least one valid choice of (l, r).
Constraints
- 2 \leq N \leq 5 \times 10^5
- 1 \leq B \leq 10^{14}
- 1 \leq P_j \leq 10^9 (1 \leq j \leq N)
- 1 \leq C_i \leq B (1 \leq i \leq N - 1)
- All input values are integers
Input
N B
P_1 P_2 \ldots P_N
C_1 C_2 \ldots C_{N-1}
- The first line contains an integer N representing the number of cherry blossom spots and an integer B representing the budget, separated by a space.
- The second line contains N integers P_1, P_2, \ldots, P_N representing the scores of each spot, separated by spaces.
- The third line contains N - 1 integers C_1, C_2, \ldots, C_{N-1} representing the maintenance costs of each promenade, separated by spaces.
Output
Print in one line the maximum satisfaction among all maintenance intervals whose total cost is at most B.
Sample Input 1
5 10 3 1 4 1 5 2 3 4 5
Sample Output 1
10
Sample Input 2
4 3 10 20 30 40 1 2 3
Sample Output 2
70
Sample Input 3
10 15 5 8 3 10 7 2 9 6 4 11 3 2 5 1 4 6 2 3 7
Sample Output 3
35
Sample Input 4
20 50 12 5 18 3 15 9 20 7 14 6 11 8 19 2 16 10 4 13 17 1 3 7 2 8 1 5 4 6 9 3 7 2 8 1 5 4 6 9 3
Sample Output 4
130
Sample Input 5
2 100000000000000 1000000000 1000000000 1
Sample Output 5
2000000000