一群 $k$ 位旅行者朋友前往贝特山（Góry Bajtowe）。最后一天，他们决定组织一场从他们所在的避难所到克拉托瓦山（Góra Kratowa）山顶的比赛。

每位朋友都拥有一张地形图，这是一个被划分为 $n$ 行 $m$ 列的矩形；因此地图总共包含 $n \cdot m$ 个区域。避难所位于地图左上角的区域，而山顶位于地图右下角的区域。克拉托瓦山以其非常均匀的坡度而闻名——对于地图上的任何区域，地图上与其相邻的右侧或下方的区域海拔更高，而左侧或上方的区域海拔更低。但这座山也因潜伏在登山爱好者身边的许多危险而闻名。地图上的一些区域被标记为非常危险，因为那里有野生动物居住——所以最好不要进入这些区域。

你是克拉托瓦山脚下避难所的管理员。通过观察 $k$ 位旅行者中的每一位，你已经为他们每个人分配了两个参数 $a_i$ 和 $b_i$，用于确定他们在山坡上的移动速度。更准确地说，对于第 $i$ 位旅行者，从任何安全区域移动到侧面相邻的区域，如果旅行者是向海拔更高的区域移动，则需要 $a_i$ 分钟；如果他是向海拔更低的区域移动，则需要 $b_i$ 分钟。你还知道，每位参赛者都会选择一条对他来说从避难所到山顶的最快路线，该路线完全位于地形图内，并且避开了所有危险区域。

你想知道最快的人到达山顶需要多少时间，以及有多少人会与获胜者同时到达山顶。你可以假设从避难所到山顶至少存在一条安全路线。

输入格式

输入的第一行包含三个正整数 $n, m$ 和 $k$ ($2 \le n, m \le 2000, 1 \le k \le 10^6$)，表示地图的大小和朋友的数量。接下来的 $n$ 行包含从上到下地图各行的描述：每一行由一个包含 $m$ 个字符的字符串组成，字符为 . 或 X，表示给定行中各区域的类型： 字符 . 表示安全区域。 字符 X 表示有野生动物居住的区域。

接下来的 $k$ 行描述了各位朋友；第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le 10^9$)，分别表示第 $i$ 位旅行者上山和下山的时间（以分钟为单位）。

避难所位于地图的左上角，即描述的第一行和第一列的交汇处。山顶位于地图的右下角，即描述的第 $n$ 行和第 $m$ 列的交汇处。你可以假设包含避难所和山顶的区域是安全的，并且在这些区域之间至少存在一条由纯安全区域组成的路径。

输出格式

在输出的第一行也是唯一一行中，输出两个数字：获胜者的比赛时间（以分钟为单位）以及达到该精确时间的旅行者人数。

样例

样例输入 1

5 7 1
......X
X.X..X.
..X.X.X
.X.X...
.....X.
2 1

样例输出 1

26 1

样例输入 2

2 5 4
.X...
...X.
2 1
2 2
1 7
2 1

样例输出 2

13 3

说明

第二个样例的解释：从避难所到克拉托瓦山顶只有一条路径。沿着这条路径，旅行者们到达山顶的时间分别为：13 分钟、14 分钟、13 分钟和 13 分钟。

子任务

在部分测试中，满足额外条件 $k = 1$。