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?
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 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.
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.
5 3 10 11 27 44 39 90 0
2
5 4 10 21 27 44 39 90 0
3
5 5 10 41 27 44 39 90 0
7
2 2 8 11 16 6
6
10 8 100 560 02 821 920 2036 5840 4212 5668 6982 7598 99
52
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.
You have a secret. There are $$$N$$$ people in your class. $$$M$$$ pairs of these people are friends with each other. If person $$$A$$$ is friends with person $$$B$$$, person $$$B$$$ is also friends with person $$$A$$$.
Every night, you choose a set of people (which may be empty) to tell the secret to. Unfortunately, friends cannot keep a secret to themselves once you tell them. Thus, every morning, every person who knows the secret tells all of their friends the secret.
For each person $$$i$$$ there is an earliest day $$$D_i$$$ on which you are willing for the person to find out the secret. For some people, $$$D_i$$$ may be $$$-1$$$, meaning that you never want them to find out the secret. While satisfying these constraints, what is the earliest day that each person can find out the secret? If they can never find out the secret, output $$$-1$$$.
Please note that even if you are willing to tell a person $$$X$$$ the secret on day $$$D_X$$$, you may choose not to do so, as it may lead (directly or indirectly) to another person $$$Y$$$ learning of the secret before day $$$D_Y$$$.
The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$. $$$N$$$ is the number of people in the class. $$$M$$$ is the number of pairs of friends in the class.
The second line of input contains $$$N$$$ space-separated integers. The $$$i$$$th of these integers represents $$$D_i$$$, the earliest day the $$$i$$$th person can find out the secret.
The following $$$M$$$ lines of input each contain two space-separated integers, $$$A_i$$$ and $$$B_i$$$. This means that person $$$A_i$$$ and $$$B_i$$$ are friends with each other.
Output $$$N$$$ space-separated integers. The $$$i$$$th of these integers should represent the earliest day the $$$i$$$th person can find out the secret, while ensuring that no person learns the secret before day $$$D_i$$$.
For all subtasks it is guaranteed that $$$1 \leq N \leq 2 \times 10^5$$$ and $$$0 \leq M \leq 2 \times 10^5$$$. Additionally, $$$1 \leq A_i \lt B_i \leq N$$$ for all $$$1 \leq i \leq M$$$. For all $$$1 \leq i \lt j \leq M$$$ it is guaranteed that at least $$$A_i \neq A_j$$$ or $$$B_i \neq B_j$$$ (or possibly both).
- Subtask 1 [3 points]: $$$M = 0$$$
- Subtask 2 [6 points]: $$$M = \frac{N \cdot (N-1)}{2}$$$
- Subtask 3 [19 points]: $$$N \leq 2000$$$ and $$$M = N - 1$$$, and $$$A_i = i$$$ and $$$B_i = i + 1$$$ for all $$$1 \leq i \leq N - 1$$$.
- Subtask 4 [19 points]: $$$M = N - 1$$$ and $$$A_i = i$$$ and $$$B_i = i + 1$$$ for all $$$1 \leq i \leq N - 1$$$
- Subtask 5 [23 points]: $$$N \leq 400$$$
- Subtask 6 [8 points]: $$$N \leq 2000$$$
- Subtask 7 [22 points]: No additional subtasks.
2 11 31 2
2 3
6 510 6 4 3 -1 61 22 61 63 44 6
10 9 7 8 -1 9
6 56 8 3 9 2 21 22 33 44 55 6
7 8 8 9 8 7
3 31 3 31 22 31 3
2 3 3
2 14 -11 2
-1 -1