题目描述

探险者要在一张方格地图中寻找宝藏。地图由 $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$。

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

12

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

本平台练习数据约定

以下是本站为本练习约定的数据范围，不作为原始题目出处的数据范围声明。

• $1 \le n,m \le 20$，$0 \le k \le 10$。
• $0 \le E \le 10^9$，$1 \le C,w_i \le 10^9$。
• 宝藏坐标满足 $1 \le x_i \le n$、$1 \le y_i \le m$；终点坐标满足 $1 \le r \le n$、$1 \le c \le m$。