Description

Suika’s environment is simplified to a grid of length $h$ and width $w$. The $X$-coordinate range is $[1, w]$, and the $Y$-coordinate range is $[1, h]$.

At the initial moment (time $1$), she stands on the cell at coordinates $(sx, sy)$.

A watermelon may appear on any cell. At each time unit, it may move in any direction or stay still. The positions and trajectories of all watermelons are known. The total number of watermelons is $n$, but only $m$ of them can be picked up by Suika; the others are too big and may hurt her.

The whole process lasts for $T$ time steps. Suika wants to pick up all $m$ small watermelons while avoiding being at the same position as any big watermelon at any time. To pick up a watermelon, she must be at the same position as that watermelon at some time step. Also, because Suika does not want to run around too much, at each time step she may either stay still or move to one of the four adjacent cells, as long as she does not leave the grid. If she moves to an adjacent cell, it counts as one move. At time $1$, Suika has just taken her position and cannot move.

At each time step, if Suika chooses to move, you may assume that Suika and the watermelons move from their old positions to their new positions simultaneously, with no order.

Suika wants to know the minimum number of moves needed to avoid all big watermelons and collect all $m$ small watermelons.

Input Format

The first line contains five integers $h, w, T, sx, sy$, as described above.

The second line contains two integers $n, m$, as described above.

Then follow $n$ blocks. Each block describes a watermelon's appearance time, disappearance time, movement, and whether it can be picked up:

• First line: two integers $t1, t2$, meaning the watermelon appears at time $t1$ and disappears at time $t2$. If $t2 = T + 1$, the watermelon does not disappear even at the last time step. It is guaranteed that each watermelon exists for at least one time step.
• Next line: one integer $a$, either $0$ or $1$. $0$ means this watermelon must be avoided; $1$ means this watermelon must be picked up. It is guaranteed that exactly $m$ watermelons need to be picked up.
• Next $t2 - t1$ lines: each line contains two integers $x, y$, in order describing the coordinates of this watermelon from time $t1$ to time $t2 - 1$. A watermelon’s movement may be non-continuous and happens instantaneously, so you do not need to consider whether Suika was on the movement path.

Output Format

If Suika cannot avoid being hit by any big watermelon during the $T$ time steps or cannot collect all $m$ small watermelons, output $-1$. Otherwise, output a single integer, the minimum number of moves Suika needs.

5 5 10 3 3
1 1
1 11
1
3 4
5 2
3 5
1 1
5 4
3 4
2 1
1 1
1 1
5 5

1

Hint

Sample Explanation

From times $2$ to $4$, Suika stays still. At time $6$, a watermelon appears next to her; Suika can move to $(3, 4)$ to pick it up.

Constraints and Hint

This problem uses bundled testdata.

Subtask 1: has special properties A and B.

Subtasks 2–3: has only special property A.

Subtasks 4–5: has only special property B.

Subtasks 6–10: has neither special property.

Special property A: For all watermelons, $t1 = 1, t2 = T + 1$. All watermelons stay still the whole time.

Special property B: $m = 0$.

For all subtasks, the following hold:

$1 \le x \le w, 1 \le y \le h$.

$1 \le n \le 20, 0 \le m \le 10, m \le n$.

$1 \le h, w \le 5, 1 \le T \le 100, 1 \le t1 \le T, 2 \le t2 \le T + 1, t1 < t2$.

It is guaranteed that no position will contain two or more watermelons at the same time.

Translated by ChatGPT 5