P13563 「WWOI R1」WSM 游戏

[$\texttt{WSM}$](https://gitblock.cn/Projects/769996) 是一款冒险游戏，WSM 是这个游戏的主角。

有一个由 $n$ 行 $m$ 列格子构成的地图。WSM 要从地图的左上角坐标为 $(1,1)$ 的格子出发，到达坐标为 $(a,b)$ 的格子。 地图上有 $k$ 个带有密码的锁和 $t$ 个带有密码的钥匙。 当 WSM 到达密码为 $r$ 的钥匙所在的格子，密码为 $r$ 的锁就会立刻消失。 任何一个时刻，WSM 都必须在地图内，且所处的格子必须**没有锁**。 如果某个格子中既有密码为 $r$ 的锁又有密码为 $r$ 的钥匙，那么 WSM 可以进入到这个格子。 地图上还存在着 $p$ 个普通道具和 $q$ 个魔法物品。WSM 可以消耗步数来使用地图上的普通道具和魔法物品。所有的道具和魔法物品均可重复使用。 --- 道具很原始，WSM 只能使用和自己在同一格的道具。 假设 WSM 当前位置为 $(x,y)$，使用道具后移动到 $(x',y')$。 |道具编号|移动后位置| |:-:|:-:| $1$|WSM 向上走一格，即 $(x',y')=(x-1,y)$| $2$|WSM 向下走一格，即 $(x',y')=(x+1,y)$| $3$|WSM 向左走一格，即 $(x',y')=(x,y-1)$| $4$|WSM 向右走一格，即 $(x',y')=(x,y+1)$| --- 魔法物品很脆弱，当 WSM 和某一个魔法物品处在同一格时，这个魔法物品会**永久消失**。 魔法物品很强大，WSM 可以使用地图上任意一个魔法物品。 假设 WSM 当前位置为 $(x,y)$，魔法物品的位置为 $(x_0,y_0)$，使用魔法物品后移动到 $(x',y')$。 |魔法物品编号|移动后位置| |:-:|:-:| $1$|$\frac{x+x'}{2}=x_0$，$\frac{y+y'}{2}=y_0$| $2$|$x'=x$，$\frac{y+y'}{2}=y_0$| $3$|$\frac{x+x'}{2}=x_0$，$y'=y$| WSM 每一步可以使用一个道具或一个魔法物品。请问至少需要多少步才能从坐标为 $(1,1)$ 的格子到达坐标为 $(a,b)$ 的格子？

第一行输入四个整数 $n,m,a,b$。 第二行输入四个整数 $k,t,p,q$。 接下来 $k$ 行，每行输入三个整数 $x,y,r$，表示坐标 $(x,y)$ 的格子上有密码为 $r$ 的锁。 接下来 $t$ 行，每行输入三个整数 $x,y,r$，表示坐标 $(x,y)$ 的格子上有密码为 $r$ 的钥匙。 接下来 $p$ 行，每行输入三个整数 $x,y,id$，表示坐标 $(x,y)$ 的格子上有编号为 $id$ 的道具。 接下来 $q$ 行，每行输入三个整数 $x,y,id$，表示坐标 $(x,y)$ 的格子上有编号为 $id$ 的魔法物品。

输出一个整数，表示 WSM 所需的最小步数，如果无法到达则输出 `-1`。

### 【样例 $1$ 解释】 花费最小步数的路线为： $\def\f#1{\xrightarrow{\bf 道具#1}} (1,1) \f{2} (2,1) \f{4} (2,2)$。 ### 【数据范围】 **本题采用捆绑测试。** 请注意：任意一个格子内可能**同时存在**多个锁、钥匙、道具和魔法道具。 对于所有测试数据，保证： * $1\le n,m\le400$，$1\le a\le n$，$1\le b\le m$。 * $1\le k \le 10^3$，$0\le t\le 3$，$1\le p\le 5\times 10^5$，$0\le q\le 3$。 * 对于所有的锁、钥匙、道具、魔法物品，均有 $1\le x\le n$，$1\le y\le m$。 * 对于所有的锁，均有 $1\le r\le 10^9$。 * 对于所有的钥匙，均有 $1\le r\le 10^9$。 * 对于所有的道具，均有 $id\in\{1,2,3,4\}$。 * 对于所有的魔法物品，均有 $id\in\{1,2,3\}$。 | 子任务编号 |$n,m\le$|$k\le$|$t\le$|$p\le$|$q\le$|分数| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$2$|$0$|$0$|$13$|$0$|$10$| |$2$|$10$|^|^|$300$|$3$|$10$| |$3$|^|$100$|$3$|^|^|$20$| |$4$|$400$|$0$|$0$|$5\times10^5$|$0$|$10$| |$5$|^|$3$|$3$|^|$3$|$25$| |$6$|^|$10^3$|^|^|^|$25$|