問題文

あなたは、魔物の群れに遭遇しました。魔物の群れは $N$ 匹の魔物で構成されており、あなたの目の前に縦一列に並んでいます。前から $i$ 番目の魔物の体力は $h_i$ です。

あなたは、以下の $2$ 種類の攻撃を使い分けることによって、全ての魔物を倒すことにしました。

• 剣で攻撃する。一番前の生き残っている魔物に、その魔物の残りの体力と同じ分のダメージを与える。
• 槍で攻撃する。全ての生き残っている魔物に、 $1$ ダメージずつ与える。

体力が $0$ となった魔物は消滅します。

あなたには、直属の上官が $2$ 人居ます。攻撃を行うたびに、その $1$ 回の攻撃で与えたダメージ量に応じて上官からボーナスとして勲章が与えられます。

$1$ 人目の上官からは、魔物に与えたダメージの合計が $k_1$ 以上であれば、赤い勲章が $1$ つ与えられます。
$2$ 人目の上官からは、魔物に与えたダメージの合計が $k_2$ 以上であれば、青い勲章が $1$ つ与えられます。

全ての魔物を消滅させたとき、持っている赤い勲章と青い勲章の合計個数としてあり得る最大値を求めてください。

制約

• 入力は全て整数
• $1 \le N \le 2 \times 10^5$
• $1 \le k_1 \le k_2 \le 2 \times 10^5$
• $1 \le h_i \le 2 \times 10^5$

部分点

• $k_1 = k_2$ を満たすデータセットに正解した場合は $30$ 点が与えられる。

入力例 1Copy

4 2 3
3 2 1 1

出力例 1Copy

4

次のように攻撃を行えばよいです。

• 剣で攻撃する。$3$ ダメージを与え、赤い勲章と青い勲章が与えられる。
• 剣で攻撃する。$2$ ダメージを与え、赤い勲章が与えられる。
• 槍で攻撃する。$2$ ダメージを与え、赤い勲章が与えられる。

入力例 2Copy

5 4 5
2 2 2 2 2

出力例 2Copy

4

入力例 3Copy

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

出力例 3Copy

16