CF505E Mr. Kitayuta vs. Bamboos

北方立田先生的花园里种植着 $ n $ 棵竹子。（竹子是一种高大、快速生长、茎中空的热带植物。）目前，第 $ i $ 棵竹子的高度为 $ h_{i} $ 米，并且每一天结束时会生长 $ a_{i} $ 米。 事实上，北方立田先生非常讨厌这些竹子。他曾尝试砍倒它们，但由于竹子的茎太硬，没能成功。不过，北方立田先生并没有放弃。他用自己的智慧制作出了一把魔法锤，试图将竹子砸进地里。 由于魔法力量有限，他每天最多只能用魔法锤敲打竹子 $ k $ 次。每次用魔法锤敲打某棵竹子时，该竹子的高度会减少 $ p $ 米。如果因此高度变为负数，则高度会变为 $ 0 $ 米（竹子不会消失）。换句话说，如果一棵高度为 $ h $ 米的竹子被魔法锤敲打一次，新的高度会变为 $ \max(0, h - p) $ 米。每天可以多次敲打同一棵竹子。 北方立田先生将从今天起与这些竹子斗争 $ m $ 天。在 $ m $ 天后（即执行 $ m $ 次“敲打竹子，然后竹子生长”的操作后），他希望使最高的竹子高度最小。请计算 $ m $ 天后，最高竹子的最低可能高度。

输入的第一行包含四个用空格分隔的整数 $ n $、$ m $、$ k $ 和 $ p $（$ 1 \leq n \leq 10^{5} $，$ 1 \leq m \leq 5000 $，$ 1 \leq k \leq 10 $，$ 1 \leq p \leq 10^{9} $），分别表示竹子的数量、与竹子斗争的天数、每天最多使用魔法锤的次数、以及魔法锤的威力。 接下来的 $ n $ 行每行包含两个用空格分隔的整数 $ h_{i} $ 和 $ a_{i} $（$ 0 \leq h_{i} \leq 10^{9} $，$ 1 \leq a_{i} \leq 10^{9} $），表示第 $ i $ 棵竹子的初始高度和每天的生长速度。

输出 $ m $ 天后，最高竹子的最低可能高度。

由 ChatGPT 5 翻译