问题描述

台风过后，城市变成一片泽国。你驾驶冲锋舟从左上角 (0,0) 出发，前往右下角 (R-1, C-1) 的安全集结点。

地图为 R × C 的网格，每个格子为以下两种之一：

• 0：可通行的水面
• 1：不可通行的障碍（倒塌建筑）

冲锋舟有初始体力 HP，每移动一步（向上下左右）消耗 1 点体力。
当体力降为 0 或负数 时，任务失败，无法继续前进（若恰好到达终点且体力耗尽，仍视为成功，但后续无法再移动）。

地图上有 K 名群众，每个群众有一个生命值 life，并给出其坐标（保证该坐标在地图上为 0，且不在起点和终点）。
当你第一次到达某个群众所在的格子时，你可以选择：

• 救援：消耗 life 点额外体力（在移动消耗的基础上），并获得 life 点荣誉值。
• 忽略：不消耗额外体力，不获得荣誉值。

注意：每个群众只能被救援一次，且救援决定必须在到达该格子的那一刻做出。

目标：在体力耗尽之前（即到达终点时体力 ≥ 0）规划一条从起点到终点的路径（不重复经过已走过的格子），使得：

• 第一优先级：获得的总荣誉值最大；
• 第二优先级：在荣誉值相同的情况下，到达终点时剩余体力最多。

如果无法在体力耗尽之前找到任何一条到达终点的路径，则任务失败。

输入格式

第一行包含两个整数 R 和 C，分别表示地图的行数和列数。
第二行包含一个整数 HP，表示冲锋舟的初始体力。
接下来 R 行，每行包含 C 个整数（0 或 1），描述地图，其中 0 表示可通行，1 表示障碍。
下一行包含一个整数 K，表示群众的总数。
接下来 K 行，每行包含三个整数 x y life，分别表示群众的坐标（行号、列号）和生命值。

约束：

• 1 ≤ R, C ≤ 8
• 1 ≤ HP ≤ 30
• 0 ≤ K ≤ 6
• 所有群众的坐标保证在地图范围内，且对应格子为 0，并且不在起点 (0,0) 和终点 (R-1, C-1) 上。
• 保证至少存在一条从起点到终点的路径（不考虑体力限制时）。

输出格式

• 如果无法完成任务，则输出一行 -1 -1。
• 否则，输出一行两个整数，用空格分隔：最大荣誉值 和 救援人数（即被救援的群众个数）。

样例

样例输入 1

2 3
10
0 0 0
0 0 0
2
0 1 1
1 1 2

样例输出 1

3 2

样例输入 2

3 3
10
0 0 0
0 1 0
0 0 0
2
0 1 3
2 1 2

样例输出 2

3 1