怪兽的初始血量是整数 hp。你会和它打 n 个回合,第 i 回合开始时只能从两种动作里挑一个执行:刀砍,或者毒杀。
如果你在第 i 回合用刀砍,怪兽在这一回合会直接损失 cuts[i] 点血量,没有后续效果。如果你在第 i 回合用毒杀,怪兽在这一回合不会损失血量,但从下一回合开始,每一回合都会损失 poisons[i] 点血量;而且你之前所有毒杀动作产生的掉血效果会一直叠加,直到怪兽死亡。
如果 n 个回合内怪兽都没有死,你就无法再做出新的动作了;但如果怪兽身上还有中毒效果,它仍会继续掉血,直到血量耗尽的那一刻才会死亡。请你算出:怪兽最早会在第几回合死亡。
第一行,两个整数 n、hp,分别表示回合数与怪兽的初始血量。
第二行,n 个正整数 cuts[1], cuts[2], ..., cuts[n],表示第 i 回合用刀砍造成的伤害。
第三行,n 个正整数 poisons[1], poisons[2], ..., poisons[n],表示第 i 回合用毒杀产生的中毒伤害。
输出一个整数,表示怪兽最早在第几回合死亡。
2 12 3 2 4 3
4
对于所有数据,1 ≤ n ≤ 10^5,1 ≤ hp ≤ 10^9,1 ≤ cuts[i], poisons[i] ≤ 10^9。每个测试点的具体限制见下表:
| 测试点编号 | 约束 |
|---|---|
| 1~3 | n ≤ 18,hp ≤ 1000 |
| 4~7 | n ≤ 2000 |
| 8~10 | 没有其他限制 |