题目背景

伊吹萃香 (Ibuki Suika) 正在魔法之森漫步，突然，许多西瓜 (Suika) 从四周飞来，划出了绚丽的轨迹。虽然阵势有点恐怖，但她还是决定抱走一些西瓜。

题目描述

萃香所处的环境被简化为一个长为 $h$，宽为 $w$ 的网格平面。$X$ 坐标范围为 $[1,w]$，$Y$ 坐标范围为 $[1,h]$。

她初始时（第 $1$ 个时刻）站在坐标为 $(sx,sy)$ 的方格。

西瓜可能在任意一个方格出现，在每个时间单位，它们可能向任何一个方向移动，也可能静止不动。西瓜的位置和移动的轨迹是已知的。西瓜的总数为 $n$ 个，但只有 $m$ 个西瓜可以被萃香抱走，因为其他都太大了，可能会砸伤她。

整个过程会持续 $T$ 个时刻。萃香希望可以抱走全部的 $m$ 个西瓜，并且在任何时候避免与任何一个过大的西瓜处在同一位置。抱走的方式为在某个时刻，与该西瓜处于同一位置。另外，由于萃香不愿耗费过多体力到处乱跑，她每个时刻可以选择静止不动，也可以选择移动到相邻的四个格子之一，只要不越出环境边界。如果选择移动到相邻格子，则算作移动了一次。第 $1$ 个时刻萃香刚站定，无法移动。

在每个时刻，如果萃香选择移动，可以认为萃香与西瓜同时从原来的位置移到了新的位置，没有先后顺序。

萃香想要知道，不被任何一个大西瓜砸中，并得到所有的m个小西瓜的情况下，最少需要移动多少次。

输入格式

第一行五个整数 $h,w,T,sx,sy$ ，含义见题目描述。

第二行两个整数 $n,m$，含义见题目描述。

接下来 $n$ 段数据，每一段描述了一个西瓜的出现位置，时间，移动方式，是否可以被抱走等内容，具体如下:

首先一行，两个整数 $t1,t2$，表示西瓜在 $t1$ 时刻出现，$t2$ 时刻消失。若 $t2=T+1$，表示西瓜在最后一个时刻也不消失。保证西瓜至少存在一个时刻。

接下来一行一个整数 $a$，只能为 $0$ 或 $1$，$0$ 表示这个西瓜需要避开，$1$ 表示这个西瓜需要抱走。数据保证需要抱走的西瓜恰好有 $m$ 个。

接下来 $t2-t1$ 行，每一行两个整数 $x,y$，顺序描述了从 $t1$ 时刻到 $t2-1$ 时刻，该西瓜的坐标。西瓜的移动不一定是连续的，并且是一瞬间完成的，所以无需考虑萃香是否站在了移动路径上。

输出格式

如果萃香在整个 $T$ 时刻内无法避免被大西瓜砸中或者无法收集到所有 $m$ 个小西瓜，输出 $-1$，否则输出一个整数，表示萃香需要移动的最少次数。

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

提示

样例说明

第 $2 \sim 4$ 个时刻萃香站着不动，在第 $6$ 个时刻，西瓜出现在萃香旁边，萃香移动到 $(3,4)$ 位置即可抱走这个西瓜。

数据范围和提示

本题采用捆绑测试。

Subtask $1$：具有特殊性质 A 和 B；

Subtask $2 \sim 3$：仅具有特殊性质 A；

Subtask $4 \sim 5$：仅具有特殊性质 B；

Subtask $6 \sim 10$：不具有任何一个特殊性质。

特殊性质 A：对于所有西瓜，均满足 $t1=1,t2=T+1$。 所有西瓜全程都静止在原地，不会发生移动。

特殊性质 B：$m=0$。

对于全部子任务，满足：

$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$

保证一个位置不会同时出现两个或两个以上西瓜。