P8170 [eJOI 2021] Waterfront

现有 $N$ 丛初始高度为 $\textit{height}_i$ 的灌木。每丛灌木每天都会生长 $\textit{dailyGrowth}_i$ 的高度。 每天在**灌木生长完毕后**，园丁将对灌木剪枝 $k$ 次。每次可以将任意一丛高度不小于 $x$ 的灌木剪短 $x$ 个单位。 求 $M$ 天后最高的一丛灌木的高度的最小值。

第一行四个正整数 $N,M,k,x$。 接下来的 $N$ 行，每行两个非负整数 $\textit{height}_i,\textit{dailyGrowth}_i$。

一个非负整数，表示 $M$ 天后最高的一丛灌木的高度的最小值。

#### 样例解释 |天数|灌木编号|高度变化量| | :----------: | :----------: | :----------: | |$1$|$1 \\ 2 \\ 3 \\ 4$|$2 \overset{+5}{\to} 7 \overset{-3}{\to} 4 \\ 3 \overset{+2}{\to} 5 \\ 0 \overset{+4}{\to} 4 \\ 2 \overset{+8}{\to} 10 \overset{-3}{\to} 7 \overset{-3}{\to} 4 \overset{-3}{\to} 1$| |$2$|$1 \\ 2 \\ 3 \\ 4$|$4 \overset{+5}{\to} 9 \overset{-3}{\to} 6 \overset{-3}{\to} 3 \\ 5 \overset{+2}{\to} 7 \\ 4 \overset{+4}{\to} 8 \\ 1 \overset{+8}{\to} 9 \overset{-3}{\to} 6 \overset{-3}{\to} 3$| |$3$|$1 \\ 2 \\ 3 \\ 4$|$3 \overset{+5}{\to} 8 \\ 7 \overset{+2}{\to} 9 \overset{-3}{\to} 6 \\ 8 \overset{+4}{\to} 12 \overset{-3}{\to} 9 \overset{-3}{\to} 6 \\ 3 \overset{+8}{\to} 11 \overset{-3}{\to} 8$| #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（8 pts）：$1 \le N \le 100$，$M=k=x=1$，$\textit{height}_i \ge 1$，$\textit{dailyGrowth}_i=0$。 - Subtask 2（22 pts）：$1 \le N,M \le 500$。 - Subtask 3（43 pts）：$1 \le N,M \le 5000$。 - Subtask 4（27 pts）：$1 \le N,M \le 10^4$。 对于 $100\%$ 的数据，$1 \le k \le 1000$，$1 \le x \le 10^4$，$0 \le \textit{height}_i,\textit{dailyGrowth}_i \le 10^4$。 #### 说明 本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 2 C Waterfront。