该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

做好了_╬_，你发现来的路已经消失，面前有一个迷宫，旁边有一张地图。

问题描述

迷宫的外形是一个长方形，其南北方向被划分为\(n\)行，东西方向被划分为\(m\)列， 于是整个迷宫被划分为\(n\)×\(m\)个单元。每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。南北或东西方向相邻的2个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成\(p\)类， 打开同一类的门的钥匙相同，不同类门的钥匙不同。
出口在迷宫的东南角，即(\(n\),\(m\)) 单元里。迷宫只有一个入口， 在西北角。也就是说，你可以直接进入 (1,1) 单元。另外，你从一个单元移动到另一个相邻单元的时间为1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
你想知道你走出迷宫的最短时间。

输入格式

第1行有三个整数,分别表示\(n\)，\(m\)，\(p\)的值。
第2行是一个整数\(k\)，表示迷宫中门和墙的总数。
第\(i\)+2行，有5个整数，依次为\(xi1\)，\(yi1\)，\(xi2\)，\(yi2\)，\(gi\)：

• 当\(gi\)>=1 时，表示 (\(xi1\),\(yi1\))单元与 (\(xi2\),\(yi2\)) 单元之间有一扇第\(gi\)类的门；

• 当\(gi\)=0时， 表示 (\(xi1\),\(yi1\)) 单元与 (\(xi2\),\(yi2\)) 单元之间有一堵不可逾越的墙。

  第\(k\)+3行是一个整数s，表示迷宫中存放的钥匙总数。
  第\(k\)+3+j行 ，有3个整数，依次为\(xi1\)，\(yi1\)，\(qi\)，表示第\(j\)把钥匙存放在 (\(xi1\),\(yi1\)) 单元里，并且第\(j\)把钥匙是用来开启第\(qi\)类门。

  输出格式

  输出你到达出口的最短时间。如果问题无解，则输出 −1。

  样例数据

  样例输入1

  4 4 9
  9
  1 2 1 3 2
  1 2 2 2 0
  2 1 2 2 0
  2 1 3 1 0 
  2 3 3 3 0
  2 4 3 4 1
  3 2 3 3 0
  3 3 4 3 0
  4 3 4 4 0
  2
  2 1 2 
  4 2 1
  

  样例输出1

  14
  

提示

• 数据范围

  对于%100的数据，|\(xi1\) − \(xi2\)| + |\(yi1\) − \(yi2\)| = 1，0 <= \(gi\) <= \(p1\) <= \(qi\) <= \(pn\)，\(m\)，\(p\) <= 10，\(k\) < 150；

限制

时间限制：1s。
空间限制：256MB。