P9107 [PA 2020] Wycieczka górska

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 4 [Wycieczka górska](https://sio2.mimuw.edu.pl/c/pa-2020-1/wyc/)** 一群 $k$ 个旅行者朋友去了 Byte 山。在最后一天，他们决定组织一场登山比赛，从他们所住的旅店到 Byte 山顶。 每个旅行者都有一张区域地图，它是一个分为 $n$ 行 $m$ 列的矩形；因此地图一共包含 $n\cdot m$ 个区域。旅店位于地图左上角的区域，而山顶则位于地图右下角的区域。Byte 山以其非常均匀而闻名——对于地图上的任何区域，在地图上与之相邻的右面或下面的区域海拔较高，而相邻的左边或上面区域海拔较低。但是，这座山也因潜伏着许多危险地区而闻名。有些地区在地图上标明是非常危险的，因为那里有野生动物居住——所以最好不要到那里去…… 你是 Byte 山山脚下的一个小屋的看守人。通过观察每一个旅行者，你已经为他们每个人分配了两个参数 $a_i$ 和 $b_i$，这些参数决定了他们在山坡上的运动速度。具体来说，如果第 $i$ 个旅行者向更高的区域移动，那么他需要 $a_i$ 分钟，如果旅行者向更低的区域移动，则需要 $b_i$ 分钟。你也知道，每个旅行者都会走对他们来说从小屋到山顶最快的路线，并且路线完全在地形图上，而且避开了所有的危险区域。 你想知道最快的人需要多长时间才能到达山顶，有多少人将与最快的人同时爬到山顶。你可以假设，从小屋到山顶至少有一条安全的路线。

第一行三个整数 $n,m,k$，分别表示地图的大小和旅行者的数量。 接下来 $n$ 行包含对地图的描述，每行由一个包含 $m$ 个字符的字符串组成，字符串中只包含 $\texttt{.}$（点）和 $\texttt X$，表示每个区域： - $\texttt .$ 表示这是一个安全区域。 - $\texttt X$ 表示这个区域有野生动物定居，是危险的。 接下来 $k$ 行描述每个旅行者。每行包含两个整数 $a_i,b_i$，分别表示第 $i$ 个旅行者向更高或更低区域移动所要花费的时间。 旅店位于地图的左上角，在地图的第一行第一列。山顶在地图的右下角，在地图的第 $n$ 行第 $m$ 列。你可以假设包含旅店和山顶的区域是安全的，而且这些区域之间至少有一条只由安全区域组成的路径。

输出一行两个整数，分别表示最先到达山顶的旅行者的用时和用时等于最小用时的旅行者的数量。

#### 样例 2 解释 从旅店到山顶只有一条路径，这些旅行者的用时分别是 $13,14,13,13$。 ------------ #### 数据范围 **本题采用捆绑测试** 对于一些子任务满足 $k=1$。 对于 $100\%$ 的数据，保证 $2\le n,m\le 2\times 10^3$，$1\le k\le 10^6$，$1\le a_i,b_i\le 10^9$。