24071번 - Waterfront 서브태스크다국어

On the waterfront of the Prahova River, the Mayor of Ploieşti planted a row of $N$ ornamental tree shrubs of various varieties, each tree shrub $i$ initially having the height $height[i]$, $1 ≤ i ≤ N$. Depending on the soil in which it is planted and the weather, the shrub $i$ grows daily with height $dailyGrowth[i]$.

Every day the town hall gardener adjusts the height of the tree shrubs by cutting them with scissors. However, the gardener is limited by the quality of the scissors. Thus, with one cut they can cut off exactly $x$ centimeters from the height of a shrub tree if the height is at least $x$ centimeters (note that the tree shrub may reach height $0$ after a cut). In order not to get tired, the gardener can perform at most $k$ cuts in a day. The gardener can make several cuts on the same tree shrub in one day.

The mayor organizes an artistic event after $M$ days and wants to know what is the minimum possible height of the tallest tree shrub after the $M$ days.

Note! Every day, the trees grow first, and then the cuts are done.

The first line contains $N$, $M$, $k$ and $x$. Of the following $N$ lines, the $i$^th contains $height[i]$ and $dailyGrowth[i]$, separated by a single space.

Output a non-negative integer, representing the minimum height of the tallest tree shrub, after the $M$ days.

• $1 ≤ k ≤ 1\,000$
• $1 ≤ x ≤ 10\,000$
• $0 ≤ height[i] ≤ 10\,000$
• $0 ≤ dailyGrowth[i] ≤ 10\,000$

The gardener cuts the trees in $3$ days, making $4$ cuts every day. At each cut they can remove $3$ centimeters from the height of one tree. The following table summarises the optimal way to make the cuts.