有一天，一位名叫 James 的猎人来到一个神秘区域寻找宝藏。James 想要探索该区域并带走他能找到的所有宝藏。

该区域可以用一个 $N \times M$ 的矩形表示。矩形中的每个点都有一个数字，表示探索该点的代价；$-1$ 表示 James 无法通过该点。James 可以从矩形外的任何位置开始，逐点进行探索。他将在矩形内移动，并带走他能拿到的所有宝藏。当然，他最终会到达矩形的任意边界并离开（James 在经过任何点时都会对其进行探索，因为他不记得该点是否已被探索过）。

现在给你该区域的地图，你必须计算出 James 带走他能拿到的所有宝藏所需的最小代价（一个点最多只能对应一个宝藏）。此外，如果 James 什么也拿不到，请输出 0。

输入格式

输入包含 $T$ 组测试数据。第一行给出测试数据的组数 $T$。每组测试数据的第一行包含两个整数 $N, M$ ($1 \le N, M \le 200$)，表示矩形的大小。接下来的 $N$ 行，每行包含 $M$ 个数字（$0 \sim 9$），表示每个点的代价。接下来是一个整数 $K$ ($1 \le K \le 13$)，随后有 $K$ 行，每行包含两个整数 $x, y$，表示宝藏的位置，$x$ 表示行号（从 0 开始），$y$ 表示列号（从 0 开始）。

输出格式

对于每组测试数据，仅输出一个数字，表示最小代价。

样例

输入 1

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

输出 1

8
11