Minimize the Maximum Bush Height

You are given N bushes. The i^th bush initially has height \(\textit{height}_i\) and grows daily by \(\textit{dailyGrowth}_i\) units. The process lasts for M days.

Each day, after all bushes grow, the gardener performs k pruning operations. During each pruning operation, the gardener may choose any bush whose current height is at least \(x\) and reduce its height by exactly \(x\) units.

Your task is to determine the minimum possible value of the maximum bush height after M days if the gardener prunes optimally.

Hint: You may use a binary search over the final maximum height and check if it is possible to achieve that height with at most \(M \times k\) prunings. For a bush i, if its unpruned height after M days is \(H_i = \textit{height}_i + M \times \textit{dailyGrowth}_i\), then the number of prunings needed to reduce its height to at most \(T\) is \(\max\Big(0, \Big\lceil\frac{H_i - T}{x}\Big\rceil\Big)\).

inputFormat

The first line contains four integers: N, M, k, and x.

The second line contains N integers \(\textit{height}_1, \textit{height}_2, \ldots, \textit{height}_N\).

The third line contains N integers \(\textit{dailyGrowth}_1, \textit{dailyGrowth}_2, \ldots, \textit{dailyGrowth}_N\).

outputFormat

Output a single integer, which is the minimum possible value of the maximum bush height after M days that can be achieved with at most M * k pruning operations.

sample

3 5 2 3
1 2 3
1 1 1

-2