题目描述

青蛙哥种了 $n$ 棵竹子，一开始第 $i$ 棵竹子的高度为 $h_i$ ，每天会长高 $a_i$ 。由于竹子长得太快，青蛙哥不得不砍掉一些竹子，但是，每次只能砍下一截长度为 $p$ 的竹子，而且为了防止刀具磨损，青蛙哥每天只能用刀砍 $k$ 次。如果一个竹子的高度不足 $p$，显然砍完之后高度不能为负数，而应该是 $0$ 。

青蛙哥想知道，他砍了 $m$ 天之后，最高的一棵竹子的最低高度是多少。每天先砍竹子，砍完后竹子才会生长。

输入格式

第一行输入四个正整数，分别为 $n$、$m$、$k$、$p$ 。

接下来 $n$ 行，每行一个非负整数 $h_i$ 和一个正整数 $a_i$ 。

输出格式

输出一个数，表示最高的一棵竹子的最低高度。

样例输入1

3 1 2 5
10 10
10 10
15 2

样例输出1

17

样例2

见下发文件。

数据范围

对于 $15\%$ 的数据，满足 $n\le 2$。

对于另外 $15\%$ 的数据，满足 $n\le 1000$ ，$m\le 50$ 。

对于另外 $40\%$ 的数据，满足 $n\le 5000$。

对于 $100\%$ 的数据，满足 $n \le 10^5$ ，$m \le 5000$ ，$k \le 10$ ，$p,h_i,a_i\le 10^9$ 。