题目：营救大兵瑞恩

题目描述

1944 年，特种兵麦克接到国防部命令，需立刻赶赴太平洋孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫中，麦克获取了迷宫地形图。迷宫呈长方形，南北方向划分为 $n$ 行，东西方向划分为 $m$ 列，共 $n×m$ 个单元，单元位置用有序数对（行号，列号）表示。

相邻单元间可能互通，也可能有锁着的门或不可逾越的墙。迷宫中部分单元存放着钥匙，门分为 $p$ 类，同一类门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫东南角的 $(n, m)$ 单元且已昏迷，迷宫入口在西北角的 $(1, 1)$ 单元。麦克从一个单元移动到相邻单元耗时为 1，拿钥匙及开门时间忽略不计。需设计算法，助麦克以最快方式到达瑞恩所在单元实施营救。

输入格式

• 第一行：三个整数 $n$、$m$、$p$ ，分别表示迷宫的行数、列数、门的分类数 。
• 第二行：一个整数 $k$ ，表示迷宫中门和墙的总数 。
• 第 $i + 2$ 行（$1\leq i\leq k$ ）：5 个整数 $x_{i1}, y_{i1}, x_{i2}, y_{i2}, g_{i}$ 。当 $g_{i}\geq1$ 时，表明 $(x_{i1}, y_{i1})$ 单元与 $(x_{i2}, y_{i2})$ 单元之间有第 $g_{i}$ 类的门；当 $g_{i}=0$ 时，表示两单元间有一堵不可逾越的墙 。
• 第 $k + 3$ 行：一个整数 $s$ ，表示迷宫中存放的钥匙总数 。
• 第 $k + 3 + j$ 行（$1\leq j\leq s$ ）：3 个整数 $x_{j1}, y_{j1}, q_{j}$ ，表示第 $j$ 把钥匙存放在 $(x_{j1}, y_{j1})$ 单元，且该钥匙用于开启第 $q_{j}$ 类门 。

同一行相邻整数间用一个空格分隔。

输出格式

输出麦克营救到大兵瑞恩的最短时间，若问题无解则输出 $-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

• 输出

14

数据范围与提示

• $|x_1 - x_2| + |y_1 - y_2| = 1, 0\leq g_i\leq p$
• $1\leq q_i\leq p$
• $n, m, p\leq10$，$k < 150$