242015 - 刀砍毒杀怪兽

题目描述

怪兽的初始血量是整数 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~3n ≤ 18,hp ≤ 1000
4~7n ≤ 2000
8~10没有其他限制
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 4 枚
难度 提高


上一题 下一题