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