EOJ Monthly 2019.9 (based on September Selection)
单点时限: 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
提示
输入数据规模比较大，请注意优化。