CF505E.Mr. Kitayuta vs. Bamboos

Mr. Kitayuta's garden is planted with n bamboos. (Bamboos are tall, fast-growing tropical plants with hollow stems.) At the moment, the height of the i-th bamboo is h__i meters, and it grows a__i meters at the end of each day.

Actually, Mr. Kitayuta hates these bamboos. He once attempted to cut them down, but failed because their stems are too hard. Mr. Kitayuta have not given up, however. He has crafted Magical Hammer with his intelligence to drive them into the ground.

He can use Magical Hammer at most k times during each day, due to his limited Magic Power. Each time he beat a bamboo with Magical Hammer, its height decreases by p meters. If the height would become negative by this change, it will become 0 meters instead (it does not disappear). In other words, if a bamboo whose height is h meters is beaten with Magical Hammer, its new height will be max(0, h - p) meters. It is possible to beat the same bamboo more than once in a day.

Mr. Kitayuta will fight the bamboos for m days, starting today. His purpose is to minimize the height of the tallest bamboo after m days (that is, m iterations of "Mr. Kitayuta beats the bamboos and then they grow"). Find the lowest possible height of the tallest bamboo after m days.

Kitayuta 先生的花园里种有 $n$ 棵竹子。（竹子是茎中空、生长迅速的高大热带植物。）当前，第 $i$ 棵竹子的高度为 $h_i$ 米，且每天结束时增长 $a_i$ 米。

实际上，Kitayuta 先生非常讨厌这些竹子。他曾经试图将它们砍倒，但因竹茎过于坚硬而失败。然而，Kitayuta 先生并未放弃。他凭借自己的智慧打造了一把“魔法锤”，用以将竹子砸入地下。

由于魔法力量有限，Kitayuta 先生每天最多可使用魔法锤 $k$ 次。每次用魔法锤敲击一棵竹子，其高度减少 $p$ 米；若减去后高度变为负数，则高度变为 $0$ 米（竹子不会因此消失）。换言之，若一棵高度为 $h$ 米的竹子被魔法锤敲击一次，其新高度为 $\max(0,\, h - p)$ 米。同一天内可以多次敲击同一棵竹子。

Kitayuta 先生将与竹子持续战斗 $m$ 天（从今天开始）。其目标是在 $m$ 天后（即经过 $m$ 轮“Kitayuta 先生敲击竹子，随后竹子生长”）使最高的竹子高度尽可能小。求 $m$ 天后最高竹子可能达到的最小高度。

The first line of the input contains four space-separated integers n, m, k and p (1 ≤ n ≤ 105, 1 ≤ m ≤ 5000, 1 ≤ k ≤ 10, 1 ≤ p ≤ 109). They represent the number of the bamboos in Mr. Kitayuta's garden, the duration of Mr. Kitayuta's fight in days, the maximum number of times that Mr. Kitayuta beat the bamboos during each day, and the power of Magic Hammer, respectively.

The following n lines describe the properties of the bamboos. The i-th of them (1 ≤ i ≤ n) contains two space-separated integers h__i and a__i (0 ≤ h__i ≤ 109, 1 ≤ a__i ≤ 109), denoting the initial height and the growth rate of the i-th bamboo, respectively.

输入的第一行包含四个用空格分隔的整数 $n$、$m$、$k$ 和 $p$（$1 ≤ n ≤ 10^5$，$1 ≤ m ≤ 5000$，$1 ≤ k ≤ 10$，$1 ≤ p ≤ 10^9$），分别表示北谷先生花园中竹子的数量、北谷先生战斗的持续天数、北谷先生每天最多敲击竹子的次数，以及魔法锤的威力。

接下来的 $n$ 行描述了每根竹子的属性。其中第 $i$ 行（$1 ≤ i ≤ n$）包含两个用空格分隔的整数 $h_i$ 和 $a_i$（$0 ≤ h_i ≤ 10^9$，$1 ≤ a_i ≤ 10^9$），分别表示第 $i$ 根竹子的初始高度和每日生长速率。

Print the lowest possible height of the tallest bamboo after m days.

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