EOJ Monthly 2019.9 (based on September Selection)

C. 划水

单点时限: 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$ 代表最晚的第一次攻击发生的时间。

样例

Input
5 5 5 5
1 1
2 2
3 3
4 4
5 5
Output
2
Input
1000000000 2 1 1
1 999999998
2 1
Output
100000000

提示

输入数据规模比较大,请注意优化。