Description

Xiao Ming is going to visit a classmate, but he only knows the unit and not the exact room. The unit has $n$ floors ($1, 2, \ldots, n$). Each floor has $m$ rooms ($1, 2, \ldots, m$).

Xiao Ming will start searching from some room on the first floor. His search method is special: each time he arrives at a room, if the person there is not his classmate, he will ask that person, then go to the room number (a floor and a room) told by that person. If that room is still not his classmate’s, he continues in the same way until he finds the classmate. Of course, it may be impossible to find the classmate.

His stamina is limited: for each floor he climbs, he spends $v$ stamina points. Your task is to compute the minimum stamina needed to find the classmate. If it is impossible to find the classmate, output impossible.

You may choose any starting room on floor $1$.

Input Format

The first line contains five integers $n$, $m$, $v$, $x$, $y$ (the classmate lives on floor $x$, room $y$).

Lines $2$ to $n+1$: each line contains $m \times 2$ integers. In the $(i+1)$-th line, for each $j$ from $1$ to $m$, the $(j \times 2 - 1)$-th and $(j \times 2)$-th integers denote the floor and room given by the person living on floor $i$, room $j$. (For the classmate’s own room $(x, y)$, the information is exactly their own room number, i.e., $(x, y)$.)

Output Format

Print one integer: the answer. If it is impossible to find the classmate, print impossible.

3 3 2 2 3
1 3 3 3 2 1
2 3 1 1 2 3
1 1 1 2 2 3

2

Hint

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 1000$, $1 \leq m \leq 100$, $1 \leq v \leq 50$.

Translated by ChatGPT 5