[eJOI2021] Waterfront
题目描述
现有 丛初始高度为 的灌木。每丛灌木每天都会生长 的高度。
每天在灌木生长完毕后，园丁将对灌木剪枝 次。每次可以将任意一丛高度不小于 的灌木剪短 个单位。
求 天后最高的一丛灌木的高度的最小值。
输入格式
第一行四个正整数 。
接下来的 行，每行两个非负整数 。
输出格式
一个非负整数，表示 天后最高的一丛灌木的高度的最小值。
4 3 4 3
2 5
3 2
0 4
2 8
8
提示
样例解释
| 天数 | 灌木编号 | 高度变化量 |
|---|---|---|
| $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$ | ||
| $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 \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）：，，，。
- Subtask 2（22 pts）：。
- Subtask 3（43 pts）：。
- Subtask 4（27 pts）：。
对于 的数据，，，$0 \le \textit{height}_i,\textit{dailyGrowth}_i \le 10^4$。
说明
本题译自 eJOI2021 Day 2 C Waterfront。