P9107 [PA 2020] Mountain Hike

**This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 4 [Wycieczka górska](https://sio2.mimuw.edu.pl/c/pa-2020-1/wyc/).** A group of $k$ traveler friends went to Byte Mountain. On the last day, they decided to organize a mountain climbing race from the hotel where they stayed to the top of Byte Mountain. Each traveler has a map of the area. The map is a rectangle divided into $n$ rows and $m$ columns, so it contains $n \cdot m$ cells in total. The hotel is located in the top-left cell of the map, and the summit is located in the bottom-right cell. Byte Mountain is famous for being very uniform: for any cell on the map, the adjacent cell to the right or below has a higher altitude, and the adjacent cell to the left or above has a lower altitude. However, the mountain is also known for many dangerous areas. Some cells are marked as very dangerous because wild animals live there, so it is better not to go there. You are the keeper of a hut at the foot of Byte Mountain. By observing each traveler, you assigned two parameters $a_i$ and $b_i$ to each of them, which determine their moving speed on the slope. More precisely, if traveler $i$ moves to a higher cell, it takes $a_i$ minutes; if the traveler moves to a lower cell, it takes $b_i$ minutes. You also know that each traveler will take the fastest route for them from the hut to the summit, staying entirely on the map and avoiding all dangerous cells. You want to know how long the fastest person needs to reach the summit, and how many people will reach the summit at the same time as the fastest one. You may assume that there is at least one safe route from the hut to the summit.

The first line contains three integers $n, m, k$, representing the size of the map and the number of travelers. The next $n$ lines describe the map. Each line is a string of length $m$ consisting only of $\texttt{.}$ (dot) and $\texttt{X}$, representing each cell: - $\texttt{.}$ means this is a safe cell. - $\texttt{X}$ means wild animals live in this cell, so it is dangerous. The next $k$ lines describe the travelers. Each line contains two integers $a_i, b_i$, representing the time traveler $i$ needs to move to a higher or a lower cell, respectively. The hotel is in the top-left corner of the map, in row $1$ column $1$. The summit is in the bottom-right corner of the map, in row $n$ column $m$. You may assume that the cells containing the hotel and the summit are safe, and that there is at least one path consisting only of safe cells between them.

Output one line with two integers: the time needed by the traveler who reaches the summit first, and the number of travelers whose time equals the minimum time.

#### Explanation of Sample 2 There is only one path from the hotel to the summit, and the times for these travelers are $13, 14, 13, 13$, respectively. ------------ #### Constraints **This problem uses bundled testcases.** For some subtasks, $k = 1$. For $100\%$ of the testdata, it is guaranteed that $2 \le n, m \le 2 \times 10^3$, $1 \le k \le 10^6$, and $1 \le a_i, b_i \le 10^9$. Translated by ChatGPT 5