← 返回题目列表

Codeforces · 505/E

E. 北裕太先生 vs 竹子

中文机器翻译题面 查看原题

Kitayuta先生的花园里种有n根竹子。 (竹子是高大、生长迅速的热带植物,茎中空。)目前,第 i 根竹子的高度为 hi 米,每天结束时它会长出 ai 米。

事实上,北裕太先生讨厌这些竹子。他曾经试图砍倒它们,但因为它们的茎太硬而失败了。然而北裕太先生并没有放弃。他用自己的智慧制作了魔法锤,将它们打入地下。

由于魔力有限,他每天最多可以使用魔法锤 k 次。他每用魔锤敲击一根竹子,竹子的高度就会减少p米。如果此更改导致高度变为负值,则它将变为 0 米(它不会消失)。也就是说,如果用神锤敲击一根高度为 h 米的竹子,它的新高度将为 max(0, h - p) 米。一天可以多次敲击同一根竹子。

从今天开始,Kitayuta 先生将与竹子战斗 m 天。他的目的是在m天后(即“Kitayuta先生击败竹子然后它们长大”的m次迭代)后最小化最高的竹子的高度。找出 m 天后最高的竹子的最低可能高度。

输入

输入的第一行包含四个空格分隔的整数 n、m、k 和 p (1 ≤ n ≤ 105、1 ≤ m ≤ 5000、1 ≤ k ≤ 10、1 ≤ p ≤ 109)。它们分别代表喜多裕太先生花园里的竹子数量、喜多裕多先生战斗的持续天数、喜多裕多先生每天击打竹子的最大次数以及魔锤的威力。

下面n行描述了竹子的属性。其中第 i 个(1 ≤ i ≤ n)包含两个空格分隔的整数 hi 和 ai(0 ≤ hi ≤ 109, 1 ≤ ai ≤ 109),分别表示第 i 个竹子的初始高度和生长速率。

输出

打印 m 天后最高的竹子的最低可能高度。

示例

输入 #1

3 1 2 5
10 10
10 10
15 2

输出 #1

17

输入 #2

2 10 10 1000000000
0 10
0 10

输出 #2

10

输入 #3

5 3 3 10
9 5
9 2
4 7
9 10
3 8

输出 #3

14