### 问题描述 小金来到了一个广场准备购物。广场可看作一个 $n$ 行 $m$ 列的迷宫。小金提前列好了购物清单，这份购物清单指出了她需要去到的 $k$ 家店铺在广场中的坐标以及它们从此刻开始距离关门还有多少分钟。假定小金在广场中每移动一格需要一分钟，在每家店铺里需要滞留三分钟。小金需要从给定的起点开始，在每一家商店关门之前及时赶到并完成购物，并最终到达给定终点乘车回家。请帮她计算出完成这一过程所需要的最短时间。 ### 输入 第 $1$ 行为两个数 $n,m$，表示广场大小。 第 $2\sim n+1$ 行，每行 $m$ 个数，表示广场（迷宫）地图。数字为 $0$ 可通行，为 $1$ 则不可通行。 第 $n+2$ 行为四个数 $x1,y1,x2,y2$，表示给定的起点和终点坐标。 第 $n+3$ 行为一个数 $k$，表示小金需要到达的商店数。 第 $n+4\sim n+3+k$ 行，每行包括 $xi,yi,ti$ 三个数，表示第 $i$ 家商店坐标为 $(xi,yi)$，且从出发时刻算起，距离关门还有 $ti$ 分钟。 ### 输出 一个数，表示最少所需时间。如果无法完成购物目标，输出 $-1$。 ### 输入样例 ```text 7 7 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 2 1 6 7 1 6 2 50 ``` ### 输出样例 ```text 17 ``` ### 数据范围 $3\leq n,m\leq 200$，$1\leq k\leq 15$。 上述所有起点、终点以及商店的坐标保证可达。