题目描述

一个 $N$ 行 $M$ 列方格组成的迷宫，迷宫中的方格有 $T$ 处障碍，障碍处无法通过，迷宫外被一圈障碍包围。迷宫正常能通行的方格中有 $P$ 个方格是一些特殊方格，通过这些方格耗费的时间分别为 $w_i$ 个单位时间，通过其他非特殊的方格耗费的时间均为 $1$ 个单位时间。现在从迷宫 $x1$ 行 $y1$ 列处的方格出发，要前往迷宫 $x2$ 行 $y2$ 列处的方格，计算所有方案中，耗费的最短时间。

已知在迷宫中只能上下左右四个方向移动到不是障碍的方格，并且每次只能移动一步。

输入格式

第一行是 $4$ 个正整数 $N,M,T,P$；

接下来有 $T$ 行，每行是两个整数 $x_j,y_j$，表示迷宫的 $x_j$ 行 $y_j$ 列处是障碍；

接下来有 $P$ 行，每行是三个整数 $x_i,y_i,w_i$，表示通过迷宫的 $x_i$ 行 $y_i$ 列处的特殊方格耗时 $w_i$ 个单位时间；

接下来有 $1$ 行 $4$ 个整数，分别是题目描述中的 $x1,y1,x2,y2$。

输出格式

一个整数。就是所有方案中，耗费的最短时间（多少个单位时间）。如果没有满足条件的方案，输出 $-1$。

输入输出样例

3 3 2 3
1 3
3 2
1 2 3
2 1 2
2 3 5
1 1 3 3

10

说明/提示

👀️ 对于$100\%$ 的数据，$2 \leq N,M \leq 1000,1 \leq T,P \leq N*M,T+P\leq N*M,2 \leq W_i \leq 100,1 \leq x1,x2,x_i,x_j\leq N,1 \leq y1,y2,y_i,y_j\leq M$，保证起点方格和终点方格不是障碍。