A group of $k$ traveler friends went to the Byte Mountains. On the last day, they decided to organize a race from the shelter where they are staying to the summit of Kratowa Mountain.

Each friend has a map of the area, which is a rectangle divided into $n$ rows and $m$ columns; thus, the map contains a total of $n \cdot m$ areas. The shelter is located in the area at the top-left corner of the map, and the mountain summit is in the area at the bottom-right corner. Kratowa Mountain is famous for its very uniform ascent – for any area on the map, the areas adjacent to it on the map to the right or below are located higher above sea level, and the areas adjacent to the left or above are located lower. However, the mountain is also known for many dangers that lurk for amateur mountain climbers. Some areas are marked on the map as very dangerous because they are inhabited by wild animals – it is better not to enter them.

You are the caretaker of the shelter at the foot of Kratowa Mountain. By observing each of the $k$ travelers, you have managed to assign two parameters $a_i$ and $b_i$ to each of them, which determine their speed of movement along the mountain slope. Specifically, for the $i$-th traveler, moving from any safe area to an adjacent area takes $a_i$ minutes if the traveler is moving to an area located higher, and $b_i$ minutes if they are moving to an area located lower. You also know that each participant in the race will choose the fastest route for them from the shelter to the mountain summit that lies entirely within the map and avoids all dangerous areas.

You are wondering how long it will take for the fastest person to reach the summit and how many people will reach the summit at the same time as the winner. You can assume that there is at least one safe route from the shelter to the summit.

Input

The first line of the input contains three positive integers $n$, $m$, and $k$ ($2 \le n, m \le 2000$, $1 \le k \le 10^6$) representing the size of the map and the number of friends. The next $n$ lines contain the description of the map rows from top to bottom: each consists of a string containing $m$ characters . (dot) or X, representing the types of areas in the given row: The character . denotes a safe area. The character X denotes an area inhabited by wild animals.

The next $k$ lines describe the individual friends; the $i$-th of these contains two integers $a_i, b_i$ ($1 \le a_i, b_i \le 10^9$) representing the time (in minutes) of climbing up and descending down for the $i$-th traveler, respectively.

The shelter is located in the top-left corner of the map, at the intersection of the first row and the first column of the description. The summit of the mountain is located in the bottom-right corner of the map, at the intersection of the $n$-th row and the $m$-th column of the description. You can assume that the areas containing the shelter and the mountain summit are safe and that there is at least one path between these areas consisting only of safe areas.

Output

In the first and only line of the output, print two numbers: the winner's time in minutes and the number of travelers who will reach the summit in exactly that time.

Examples

Input 1

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

Output 1

26 1

Input 2

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

Output 2

13 3

Note

Explanation of the second example: There is only one path from the shelter to the summit of Kratowa Mountain. Following it, the travelers will reach the summit: after 13 minutes, after 14 minutes, after 13 minutes, and after 13 minutes.

Subtasks

In some tests, the additional condition $k = 1$ holds.