「eJOI2021」河畔
题目描述
本题译自 eJOI2021 Problem F. Waterfront
普洛耶什蒂（Ploiești）市市长在普拉霍瓦河（Prahova River）畔种了一排 棵不同品种的观赏性灌木。每棵灌木初始高度为 。根据种植的土壤条件和天气状态，第 棵灌木每天生长的高度为 。
每天，市政厅的园丁都会通过用剪刀修建灌木来调整这些灌木的高度。然而，园丁被剪刀的质量所限制。因此对于一次修剪，如果这棵灌木至少 厘米高，那么园丁可以恰好从这棵灌木剪下 厘米的高度（注意剪完之后灌木的高度可以为 ）。为了不会很累，园丁一天可以进行最多 次修剪。在一天里园丁可以对同一灌木修剪多次。
市长会在 天后组织一次艺术活动，他希望知道在 天后最高的灌木最矮可能是多高。
注意：对于每天，树先生长，然后进行修剪。
输入格式
第一行四个整数 。
接下来 行，每行两个整数 。
输出格式
输出一个非负整数，表示 天后最高的灌木最矮可能的高度。
4 3 4 3
2 5
3 2
0 4
2 8
8
园丁会修剪 天，每天修剪 次。每次修剪可以从一棵树上剪掉 厘米。下表展示了最优修剪策略。
| 日期 | 树木 | 操作 |
|---|---|---|
| $2\stackrel{+5}{\rightarrow}7\stackrel{-3}{\rightarrow}4$ | ||
| $2\stackrel{+8}{\rightarrow}10\stackrel{-3}{\rightarrow}7\stackrel{-3}{\rightarrow}4\stackrel{-3}{\rightarrow}1$ | ||
| $4\stackrel{+5}{\rightarrow}9\stackrel{-3}{\rightarrow}6\stackrel{-3}{\rightarrow}3$ | ||
| $1\stackrel{+8}{\rightarrow}9\stackrel{-3}{\rightarrow}6\stackrel{-3}{\rightarrow}3$ | ||
| $7\stackrel{+2}{\rightarrow}9\stackrel{-3}{\rightarrow}6$ | ||
| $8\stackrel{+4}{\rightarrow}12\stackrel{-3}{\rightarrow}9\stackrel{-3}{\rightarrow}6$ | ||
| $3\stackrel{+8}{\rightarrow}11\stackrel{-3}{\rightarrow}8$ |
数据范围与提示
| # | 分值 | 限制 |
|---|---|---|