There are ~N~ trees in Bob's back yard. The trees are numbered from ~1~ to ~N~. Initially, the ~i~-th tree's height is ~h_i~, and the growth speed is ~s_i~ per day. Every day, the trees will grow in the morning. At night, Bob will adjust the height of trees by cutting them with his gardener scissors. For each cut, Bob will cut exactly ~X~ units of height from a tree if the tree's height is at least ~X~. It's possible for a tree to reach the height ~0~ after a cut, but a tree cannot reach to the negative height. Bob can cut one tree multiple times in one day. In order not to get tired, Bob will cut at most ~K~ times each day.

Bob doesn't want his tree too tall. He wants to find the minimum possible height of the tallest tree after ~M~ days. Can you write a program to help him?

Input Specification

The first line of input contains four integers ~N~, ~M~, ~K~, ~X~ (~1 \le N, M, X \le 10^4~, ~1 \le K \le 10^3~), indicating the number of trees, the number of days, the number of cuts in each day, and the length for each cut, respectively.

Each of the following ~N~ lines contains two integers ~h_i~ and ~s_i~, (~0 \le h_i, s_i \le 10^4~), indicating the initial height and the growth speed of the ~i~-th tree.

Output Specification

Output one integer, the minimum possible height of the tallest tree after ~M~ days.

Constraints

Subtask	Points	Additional constraints
~1~	~8~	~N \le 100~, ~M=1~, ~K=1~, ~X=1~.
~2~	~22~	~1 \le N, M \le 500~.
~3~	~43~	~1 \le N, M \le 5\,000~
~4~	~27~	No additional constraints.

Sample Input

4 3 4 3
2 5
3 2
0 4
2 8

Sample Output

8

Explanation for Sample

• In day ~1~, the trees initial height is ~[2, 3, 0, 2]~ and the height after growing is ~[7, 5, 4, 10]~. Bob can cut the tree ~1~ once and tree ~4~ three times. Then the tree's final height is ~[4, 5, 4, 1]~.
• In day ~2~, the trees initial height is ~[4, 5, 4, 1]~ and the height after growing is ~[9, 7, 8, 9]~. Bob can cut the tree ~1~ twice and tree ~4~ twice. Then the tree's final height is ~[3, 7, 8, 3]~.
• In day ~3~, the trees initial height is ~[3, 7, 8, 3]~ and the height after growing is ~[8, 9, 12, 11]~. Bob can cut the tree ~2~ once, cut tree ~3~ twice and cut tree ~4~ once. Then the tree's final height is ~[8, 6, 6, 8]~.

Thus, the tallest tree's height is ~8~.