配点 : 100 点
問題文
你遇到了一群魔物。魔物群由 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 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N k_1 k_2 h_1 \ldots h_N
出力
答案 请打印除以 1 行输出。
入力例 1
4 2 3 3 2 1 1
出力例 1
4
可以按如下方式进行攻击。
- 用剑攻击。3 造成伤害,并获得红色勋章和蓝色勋章。
- 用剑攻击。2 造成伤害,并获得红色勋章。
- 用矛攻击。2 造成伤害,并获得红色勋章。
入力例 2
5 4 5 2 2 2 2 2
出力例 2
4
入力例 3
15 4 7 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力例 3
16