题目背景

伊吹萃香(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~4个时刻萃香站着不动，在第6个时刻，西瓜出现在萃香旁边，萃香移动到(3,4)位置即可抱走这个西瓜。

数据范围和提示:

子任务可能出现两种特殊性质A和B

A: 所有西瓜t1=1,t2=T+1

所有西瓜全程都静止在原地，不会发生移动。

B：m=0

共有10个子任务。

对于子任务1，具有特殊性质A和B

对于子任务2~3，仅具有特殊性质A

对于子任务4~5，仅具有特殊性质B

对于子任务6~10，不具有任何一个特殊性质。

对于全部子任务

1<=所有横坐标范围<=w

1<=所有纵坐标范围<=h

1<=h,w<=5
1<=T<=100
1<=t1<=T
2<=t2<=T+1
t1<t2
1<=n<=20
0<=m<=10
m<=n

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

命题人:orangebird