P8170 [eJOI 2021] Waterfront

There are $N$ bushes with initial heights $\textit{height}_i$. Each bush grows by $\textit{dailyGrowth}_i$ in height every day. Every day, **after all bushes have finished growing**, the gardener will prune the bushes $k$ times. Each time, they may choose any bush whose height is at least $x$ and cut it shorter by $x$ units. Find the minimum possible value of the height of the tallest bush after $M$ days.

The first line contains four positive integers $N, M, k, x$. The next $N$ lines each contain two non-negative integers $\textit{height}_i, \textit{dailyGrowth}_i$.

Output one non-negative integer, the minimum possible height of the tallest bush after $M$ days.

#### Sample Explanation | Day | Bush Index | Height Change | | :----------: | :----------: | :----------: | |$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$| #### Constraints **This problem uses bundled testdata.** - 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$. For $100\%$ of the testdata, $1 \le k \le 1000$, $1 \le x \le 10^4$, $0 \le \textit{height}_i, \textit{dailyGrowth}_i \le 10^4$. #### Notes This problem is translated from [eJOI2021](https://sepi.ro/ejoi/2021) Day 2 C Waterfront。 Translated by ChatGPT 5