33 人解决,59 人已尝试。
38 份提交通过,共有 453 份提交。
5.7 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
“报告”
“说”
“肚子痛”
“去吧”
Cuber QQ 早已厌烦了在太阳的沐浴下踢正步。他每天都想方设法的在军训时间划水。
这不, Cuber QQ 假借肚子痛,实则溜回寝室打起了游戏。
现在, Cuber QQ 要给敌方小兵最后一击。
Cuber QQ 定义最后一击为,经过他的这一次攻击(也就是最后一击)的伤害结算后,小兵的生命值从正数变为 $0$ 或负数。
不过,由于小兵进入了 Cuber QQ 所在方防御塔的攻击范围,这给 Cuber QQ 的补刀增添了难度。
现在 Cuber QQ 已经知道了小兵当前生命值为 $n$ ,小兵会在 $a_i$ 时刻受到其他外界 $b_i$ 数值的伤害,总共会收到 $m$ 次伤害, Cuber QQ 的每次攻击造成的伤害 $s$ 以及 Cuber QQ 的攻击间隔 $t$。
Cuber QQ 的手速是有限的,如果他在 $x$ 时刻做出了攻击,那么他的下一次攻击最早出现的时刻将会是 $x+t$ 时刻。在 $0$ 时刻 Cuber QQ 恰好可以开始攻击。
如果 Cuber QQ 能给小兵最后一击,请输出能在小于等于 $10^8$ 时间完成给小兵最后一击的情况下第一次攻击最晚给出的时刻 $x$。
如果 Cuber QQ 无法在 $10^{8}$ 时间内给小兵最后一击,则输出 $-1$。
另外要注意的是,若在 $t$ 时刻小兵同时受到 Cuber QQ 和外界的伤害,将会先结算外界的伤害,然后再结算Cuber QQ 的伤害。
第一行有四个整数 $n,m,s,t$ ( $n,m,s,t, 1 \le n,s,t \le 10^{9}, 1 \le m \le 10^6$ )。分别代表小兵生命值,受到伤害的次数, Cuber QQ 的攻击力和攻击间隔。
之后紧跟 $m$ 行,第 $i$ 行有两个整数 $a_i,b_i$ ( $1 \le a_i,b_i \le 10^{9}$ ),表示小兵会在 $a_i$ 时间受到来自其他外界 $b_i$ 的伤害。数据保证 $a_i$ 是按顺序从小到大的。
如果无法在时间内给小兵最后一击,请输出 $-1$,否则输出一个整数 $x$ 代表最晚的第一次攻击发生的时间。
5 5 5 5 1 1 2 2 3 3 4 4 5 5
2
1000000000 2 1 1 1 999999998 2 1
100000000
输入数据规模比较大,请注意优化。
33 人解决,59 人已尝试。
38 份提交通过,共有 453 份提交。
5.7 EMB 奖励。