题目描述

探险者要在一张方格地图中寻找宝藏。地图由 $n$ 行 $m$ 列组成，探险者从左上角 $(1,1)$ 出发，最终需要到达指定终点 $(r,c)$。

探险者最初拥有 $E$ 点能量。每向上下左右相邻的可通行格移动一步，都需要消耗 $C$ 点能量。地图中有 $k$ 个宝藏，第 $i$ 个宝藏位于 $(x_i,y_i)$，价值为 $w_i$ 点能量。第一次到达该格子时可以取得宝藏并增加 $w_i$ 点能量，每个宝藏只能取得一次。

请设计一条路线，使探险者到达终点时剩余的能量最大。探险过程中能量不能小于 $0$。如果无法到达终点，输出 $-1$。

输入格式

第一行包含两个整数 $E,C$，分别表示初始能量和每移动一步消耗的能量。

第二行包含一个整数 $k$，表示宝藏数量。

接下来 $k$ 行，每行包含三个整数 $x_i,y_i,w_i$，表示一个宝藏的位置和价值。

下一行包含两个整数 $n,m$，表示地图的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数：$1$ 表示可以通行，$0$ 表示障碍物。

最后一行包含两个整数 $r,c$，表示终点位置。起点固定为 $(1,1)$。

输出格式

输出到达终点时能够剩余的最大能量。如果不存在合法路线，输出 $-1$。

样例

输入

100 2
2
1 2 1
2 2 3
3 3
1 1 0
0 1 1
0 1 1
3 2

输出

98

样例说明

探险者依次经过 $(1,2)$、$(2,2)$，最后到达 $(3,2)$，共移动 $3$ 步并取得价值总和为 $4$ 的宝藏，因此剩余能量为 $100-3\times2+4=98$。

100 2
2
1 2 1
2 2 3
3 3
1 1 0
0 1 1
0 1 1
3 2

98

33 7
1
5 1 19
5 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
2 3

-1

4 1
4
4 5 11
3 5 6
4 4 4
3 1 20
4 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 4

35