小明正在参加一场闯关游戏,一共有 n 个关卡,需要按照顺序依次挑战。
小明初始拥有 E 点能量,能量最多只能达到 M 点。
每个关卡都有一个能量消耗值 c_i。如果当前能量不少于该关卡的消耗值,就可以成功通过该关卡,并扣除对应的能量:
E=E-c_i
此外,小明还拥有 p 张补给卡。
每张补给卡可以使用一次,使用后立即恢复 R 点能量,但能量不能超过最大值 M。
也就是说,使用补给卡后:
E=\min(E+R,M)
每次挑战关卡时,小明可以选择:
如果使用补给卡后仍然无法满足当前关卡的能量要求,就无法继续闯关。
请你帮助小明计算:
注意:
第一行输入四个整数 n,E,M,R,分别表示关卡数量、初始能量、最大能量和每张补给卡的恢复量。
第二行输入一个整数 p,表示补给卡数量。
第三行输入 n 个整数:
c_1,c_2,\ldots,c_n
表示每个关卡的能量消耗。
输出一行三个整数,分别表示:
5 10 15 10 2 6 7 5 9 4
4 3 0
初始能量为 10,最多能量为 15,拥有 2 张补给卡。
| 关卡 | 操作 | 剩余能量 | 剩余补给卡 |
|---|---|---|---|
| 初始 | 初始状态 | 10 | 2 |
| 1 | 消耗 6 | 4 | 2 |
| 2 | 补充 10,再消耗 7 | 7 | 1 |
| 3 | 消耗 5 | 2 | 1 |
| 4 | 补充 10,再消耗 9 | 3 | 0 |
| 5 | 能量不足,无法继续 | 3 | 0 |
因此,小明最多通过 4 个关卡,剩余 3 点能量和 0 张补给卡。
对于所有测试数据,保证:
1\le n\le 2\times10^5
0\le E\le M\le 10^9
1\le R\le 10^9
0\le p\le 2\times10^5
1\le c_i\le 10^9