問題一覧 > 通常問題

No.2694 The Early Bird Catches The Worm

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 136
作問者 : MM / テスター : timi hibit_at mo124121 ypww
お気に入りにしたユーザー ProblemId : 10611 / 自分の提出
問題文最終更新日: 2026-10-16 13:08:06
The Early Bird Catches The Worm
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 423 (Asakatsu Presents 3) (順位表) の他の問題:

Problem Statement

Having learned the proverb "The early bird catches the worm", MM has decided to choose some consecutive days out of the next $N$ days and wake up early on them.

Strictly speaking, MM chooses one pair of integers $(L,R)$ satisfying $1\le L \le R \le N$, and wakes up early only for the $R-L+1$ days from day $L$ to day $R$.

By waking up early on day $i$ $(1\le i \le N)$, MM gains satisfaction $A_i$. On the other hand, if MM does not wake up early, the satisfaction gained on that day is $0$. The difficulty of waking up early on day $i$ is represented by $B_i$.

When MM wakes up early on day $j$ $(L\le j \le R)$, fatigue accumulates by the product of the number of days MM has woken up early so far and the difficulty, that is, by $(j-L+1)\times B_j$.

Find the maximum total satisfaction MM can gain when choosing one pair $(L,R)$ such that the total fatigue at the end of day $N$ is at most $H$.

However, if there is no pair $(L,R)$ for which the total fatigue is at most $H$, the maximum satisfaction is taken to be $0$.

Input

$N\ H$
$A_1\ \dots\ A_N$
$B_1\ \dots\ B_N$

Constraints

  • All inputs are integers.
  • $1\le N \le 2 \times 10^5$
  • $1\le H \le 10^9$
  • $1\le A_i,B_i \le 10^9 (1\le i\le N)$

Output

Output the answer in one line.

Sample

Sample 1
Input
7 22
5 10 15 20 25 30 35
10 5 4 3 2 5 10
Output
75

When $(L,R) = (4,6)$, the fatigue is $1\times B_4 + 2\times B_5 + 3\times B_6 = 22$, and MM gains satisfaction $A_4 + A_5 + A_6 =75$.

Among the pairs $(L,R)$ with fatigue at most $22$, this one gives the maximum satisfaction.

Note that when $(L,R) = (3,6)$, the satisfaction would be $90$, but the fatigue is $1\times B_3 + 2\times B_4 + 3\times B_5 + 4\times B_6 = 36 > 22$, so this pair is invalid.

Sample 2
Input
7 1
5 10 15 20 25 30 35
10 5 4 3 2 5 10
Output
0

If MM is too weak at getting up in the morning, MM cannot wake up early even for a single day. In this case, output $0$.

Sample 3
Input
7 1000000000
5 10 15 20 25 30 35
10 5 4 3 2 5 10
Output
140

If MM is extremely good at getting up in the morning, MM can keep waking up early all the way from day $1$ to day $N$.

Sample 4
Input
10 23
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8
Output
16

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。