Description

During an expedition, the archaeologist Dr. Kong was accidentally trapped inside a pyramid. Each room in the pyramid is triangular. Dr. Kong can break through a wall to move to an adjacent room. For example, if he is currently in triangular room $(2,2)$, he can break through to triangular room $(2,1)$, $(2,3)$, or $(1,1)$. However, breaking through one wall takes $K$ minutes, and Dr. Kong’s stamina only lasts for $S$ minutes.

Fortunately, Dr. Kong has a map of the pyramid and finds that there are many exits. Once he enters a triangular room that has an exit, he can leave the pyramid in $1$ minute.

Now, can you help Dr. Kong find an exit that minimizes the total time to escape? If possible, output the remaining stamina time after Dr. Kong escapes (it should be greater than or equal to $0$); otherwise, output $-1$.

Input Format

The first line contains four integers $N, M, K, S$, where:

• $N$ is the number of layers of the pyramid.
• $M$ is the number of exits.
• $K$ is the time to break through one wall.
• $S$ is the number of minutes Dr. Kong’s stamina lasts.

The second line contains two integers $X_a, Y_a$ indicating Dr. Kong’s current position.

From the third line to the $(M+2)$-th line, each line contains two integers $X_i, Y_i$ indicating the coordinates of a triangular room that has an exit.

Output Format

Output the remaining stamina time after Dr. Kong escapes; if it is impossible, output $-1$.

4 2 2 10
2 1
3 5
4 4

3

Hint

Constraints and Conventions

For all testdata, $1 \le N \le 10^6$, $0 \le M \le 10^4$, $0 < K \le 20$, $10 \le S \le 10^4$.

All numbers are integers, and values are separated by a single space.

Translated by ChatGPT 5