SuiXiang's Watermelon Rescue

SuiXiang lives in an environment modeled as a grid of height \(h\) and width \(w\) with \(X\) coordinates in \([1,w]\) and \(Y\) coordinates in \([1,h]\).

Initially (at time \(t=1\)) she stands in the cell \((sx, sy)\). There are \(n\) watermelons, but only the first \(m\) of them are small enough for her to safely pick up; the others are too big and if she ever is at the same cell as any of these big watermelons she will be hurt. The positions (and trajectories) of all watermelons over \(T\) time steps are known. For each watermelon \(i\) (\(1 \le i \le n\)), its position at time \(t\) (\(1 \le t \le T\)) is given by \((x_{i,t}, y_{i,t})\). For \(1 \le i \le m\) the watermelon is small, and for \(m+1 \le i \le n\) it is big.

At each time step starting from \(t=2\), SuiXiang may either stay in place or move to one of the four adjacent cells (up, down, left or right) provided that she remains within the grid. (At time \(t=1\) she is already placed and cannot move.) The moves are considered to happen simultaneously with the watermelons’ moves; that is, a move from one cell to an adjacent cell at time \(t\) lands her in a new cell at time \(t\) at the same moment the watermelons have moved to their new positions for that time step.

SuiXiang picks up a small watermelon at time \(t\) if she is in the same cell as that watermelon at time \(t\). She needs to pick up all \(m\) small watermelons while at no time occupying the same cell as any big watermelon. In addition, she wishes to minimize the total number of moves (i.e. the number of time steps in which she moved to an adjacent cell rather than staying still).

Given the grid dimensions, her starting position, and the trajectories of all watermelons over \(T\) time steps, determine the minimum number of moves SuiXiang must make to pick up all \(m\) small watermelons while avoiding any collision with big watermelons. If it is impossible, output \(-1\).

Note: If a small watermelon appears in the same cell as SuiXiang at the same time step, she picks it up automatically.

inputFormat

The input is given as follows:

h w T
sx sy
n m

Then, for each watermelon \(i\) from \(1\) to \(n\), a single line follows containing \(2T\) integers: \(x_{i,1} y_{i,1} x_{i,2} y_{i,2} \ldots x_{i,T} y_{i,T}\). The first \(m\) watermelons are small and can be picked up, while the remaining \(n-m\) watermelons are big and must be avoided.

All coordinates are 1-indexed and lie within the grid boundaries.

outputFormat

Output a single integer: the minimum number of moves required to pick up all the small watermelons while never being at the same cell as any big watermelon. If it is impossible, output \(-1\).

sample

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

0