[eJOI 2021] Waterfront

ID: 9191

远端评测题

1000ms

512MiB

尝试: 0

已通过: 0

难度: 7

上传者:

Hydro

标签>

2021

eJOI（欧洲）

Problem Description

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.

Input Format

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 Format

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

Hint

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$		$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$		$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 Day 2 C Waterfront。

Translated by ChatGPT 5

#P8170. [eJOI 2021] Waterfront