在普拉霍瓦河（Prahova River）的岸边，普洛耶什蒂（Ploiești）市长种植了一排 $N$ 棵观赏灌木，每棵灌木 $i$ 的初始高度为 $height[i]$，其中 $1 \le i \le N$。根据种植的土壤和天气情况，灌木 $i$ 每天会生长 $dailyGrowth[i]$ 的高度。
每天，市政园丁都会通过修剪来调整灌木的高度。然而，园丁受限于剪刀的质量：每次修剪可以从一棵高度至少为 $x$ 厘米的灌木上剪掉恰好 $x$ 厘米（注意，修剪后灌木的高度可能变为 0）。为了避免过度劳累，园丁每天最多只能进行 $k$ 次修剪。园丁可以在同一天对同一棵灌木进行多次修剪。
市长将在 $M$ 天后举办一场艺术活动，他想知道 $M$ 天后最高的那棵灌木的最小可能高度是多少。
注意！每天树木先进行生长，然后再进行修剪。
输入格式
第一行包含 $N, M, k$ 和 $x$。接下来的 $N$ 行中，第 $i$ 行包含 $height[i]$ 和 $dailyGrowth[i]$，中间用空格隔开。
输出格式
输出一个非负整数，表示 $M$ 天后最高灌木的最小可能高度。
数据范围
- $1 \le k \le 1\,000$
- $1 \le x \le 10\,000$
- $0 \le height[i] \le 10\,000$
- $0 \le dailyGrowth[i] \le 10\,000$
| # | 分值 | 数据范围 |
|---|---|---|
| 1 | 8 | $N \le 100, M = 1, k = 1, x = 1, height[i] \ge 1, dailyGrowth[i] = 0$ |
| 2 | 22 | $1 \le N, M \le 500$ |
| 3 | 43 | $1 \le N, M \le 5\,000$ |
| 4 | 27 | $1 \le N, M \le 10\,000$ |
样例
样例输入 1
4 3 4 3 2 5 3 2 0 4 2 8
样例输出 1
8
说明
园丁在 3 天内修剪树木，每天进行 4 次修剪。每次修剪可以从一棵树上移除 3 厘米的高度。下表总结了最优的修剪方式。
| 天数 | 树木 | 操作 |
|---|---|---|
| 1 | 1 | $2 \xrightarrow{+5} 7 \xrightarrow{-3} 4$ |
| 2 | $3 \xrightarrow{+2} 5$ | |
| 3 | $0 \xrightarrow{+4} 4$ | |
| 4 | $2 \xrightarrow{+8} 10 \xrightarrow{-3} 7 \xrightarrow{-3} 4 \xrightarrow{-3} 1$ | |
| 2 | 1 | $4 \xrightarrow{+5} 9 \xrightarrow{-3} 6 \xrightarrow{-3} 3$ |
| 2 | $5 \xrightarrow{+2} 7$ | |
| 3 | $4 \xrightarrow{+4} 8$ | |
| 4 | $1 \xrightarrow{+8} 9 \xrightarrow{-3} 6 \xrightarrow{-3} 3$ | |
| 3 | 1 | $3 \xrightarrow{+5} 8$ |
| 2 | $7 \xrightarrow{+2} 9 \xrightarrow{-3} 6$ | |
| 3 | $8 \xrightarrow{+4} 12 \xrightarrow{-3} 9 \xrightarrow{-3} 6$ | |
| 4 | $3 \xrightarrow{+8} 11 \xrightarrow{-3} 8$ |