A. River
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a distant city, there is a river. The river runs directly through the city and splits the city into two sides. The north side of the river has $$$K$$$ locations numbered from $$$0$$$ to $$$K-1$$$, and the south side of the river also has $$$K$$$ locations numbered from $$$0$$$ to $$$K-1$$$, both inclusive.

There are currently two ways to travel throughout the city: walking and taking a boat. For walking:

  • It is possible to travel from location $$$A$$$ on one side of the river to location $$$A+1$$$ on the same side of the river in 1 unit of time, for all $$$0 \leq A \leq K - 2$$$.
  • It is possible to travel from location $$$A$$$ on one side of the river to location $$$A-1$$$ on the same side of the river in 1 unit of time, for all $$$1 \leq A \leq K - 1$$$.

Note that you cannot walk from a location on one side of the river to a location on the other side of the river. To travel across the river, you must currently take a boat:

  • It is possible to travel from location $$$A$$$ on one side of the river to location $$$A$$$ on the other side of the river in $$$B$$$ units of time, for all $$$0 \leq A \leq K - 1$$$.

There are $$$N$$$ people living in the city. Person $$$i$$$ lives at location $$$H_i$$$ on the north side and works at location $$$W_i$$$ on the south side. Each person plans their trip as a combination of walking and taking the boat as to take the minimum possible amount of time to travel between their home and workplace.

It turns out that the boats on the rivers are hugely unsustainable and contribute to global warming! As a result, you would like to build a bridge at some location $$$L$$$, where $$$0 \leq L \leq K - 1$$$. This bridge will make it possible to walk from location $$$L$$$ on one side to location $$$L$$$ on the other side in exactly one unit of time.

However, people still want to save time, so simply building a bridge does not mean everyone will use it. The citizens have a tolerance level called $$$T$$$, which is initially $$$0$$$. Fortunately, you can run a social awareness campaign which will increase the value of $$$T$$$ for everyone in the city. A person will use the bridge if and only if their overall time taken for their travel is at most $$$T$$$ units of time more than the minimum time it would take them to travel using a boat.

You've decided that you want at least $$$M$$$ of the $$$N$$$ people in the city to start using the bridge. What is the minimum tolerance level you need everyone to have to make this happen?

Input

The first line of input contains four space-separated integers: $$$N$$$, $$$M$$$, $$$K$$$ and $$$B$$$. $$$N$$$ represents the total number of people in the city, $$$M$$$ represents the minimum number of people you want to use the bridge instead of the boat, $$$K$$$ represents the number of locations on each side of the river, and $$$B$$$ represents the time it takes to use the boat to cross the river.

The next $$$N$$$ lines of input each contain two space-separated integers $$$H_i$$$ and $$$W_i$$$. $$$H_i$$$ represents the home location of the $$$i$$$th person (on the north side) and $$$W_i$$$ represents the work location of the $$$i$$$th person (on the south side).

Output

Output a single integer $$$T$$$, the minimum possible tolerance level such that at least $$$M$$$ of the $$$N$$$ people in the city will choose to use the bridge instead of the boat.

Scoring

For all subtasks, it is guaranteed that:

  • $$$1 \leq N \leq 10^5$$$
  • $$$1 \leq M \leq N$$$
  • $$$1 \leq K \leq 10^9$$$
  • $$$1 \leq B \leq 10^9$$$
  • $$$0 \leq H_i, W_i \leq K - 1$$$ for all $$$1 \leq i \leq N$$$

Subtasks

  • Subtask 1 [3 points]: $$$M = 1$$$
  • Subtask 2 [4 points]: $$$N = 2, B = 1$$$ and $$$H_i = W_i$$$ for all $$$1 \le i \le N$$$
  • Subtask 3 [7 points]: $$$N = 2$$$
  • Subtask 4 [25 points]: $$$N, K \leq 50$$$
  • Subtask 5 [12 points]: $$$N, K \leq 1500$$$
  • Subtask 6 [13 points]: $$$N \leq 1500$$$
  • Subtask 7 [23 points]: $$$K \le 10^5, B = 1$$$ and $$$H_i = W_i$$$ for all $$$1 \le i \le N$$$
  • Subtask 8 [13 points]: No additional constraints.
Examples
Input
5 3 10 1
1 2
7 4
4 3
9 9
0 0
Output
2
Input
5 4 10 2
1 2
7 4
4 3
9 9
0 0
Output
3
Input
5 5 10 4
1 2
7 4
4 3
9 9
0 0
Output
7
Input
2 2 8 1
1 1
6 6
Output
6
Input
10 8 100 5
60 0
2 8
21 9
20 20
36 58
40 42
12 56
68 69
82 75
98 99
Output
52
Note

Sample 0 Explanation

Consider building a bridge at $$$L = 3$$$. Then, with tolerance level $$$T = 2$$$, persons numbered $$$1$$$, $$$2$$$, and $$$3$$$ will use the bridge.

For example, for person $$$1$$$:

  • His time by using the boat is $$$2$$$: $$$1$$$ unit time of walking, and then $$$B = 1$$$ unit time of using the boat to cross the river.
  • His time by using the bridge is $$$4$$$: $$$2$$$ unit times of walking till position $$$3$$$, then using the bridge in $$$1$$$ unit time, and then walking back to position $$$2$$$ in $$$1$$$ unit time.
  • Therefore, he uses the bridge because it is only $$$2 \leq T$$$ more time units.

Sample 1 Explanation

Consider building a bridge at $$$L = 2$$$. Then with tolerance level $$$T = 3$$$, we can prove that persons numbered $$$1$$$, $$$2$$$, $$$3$$$, and $$$5$$$ will use the bridge.

For example, for person $$$1$$$:

  • His time by using the boat is $$$1 + B = 3$$$.
  • His time by using the bridge is $$$1 + 1 = 2$$$.
  • Therefore, he uses the bridge as it is, in fact, even less time than the boat.