Mountain Climb Race

A group of k travelers has decided to race from their hotel to the peak of Byte Mountain. The mountain is represented by an n×m grid where each cell corresponds to a region. The hotel is located at the top‐left cell (0,0) and the peak is at the bottom‐right cell (n-1,m-1). Some regions are marked as dangerous (and are denoted by '#' on the map), and travelers must avoid these cells. It is guaranteed that both the starting and the ending cells are safe (denoted by '.') and that there is at least one safe route from the hotel to the peak.

The topography of Byte Mountain is very uniform. For every safe cell on the map, the cell immediately to its right or below is at a higher altitude, while the cell immediately to its left or above is at a lower altitude. Each traveler is given two parameters: a_i and b_i. When the i-th traveler moves to an adjacent region:

• If the move is to the right or down (i.e. an uphill move), it takes a_i minutes.
• If the move is to the left or up (i.e. a downhill move), it takes b_i minutes.

Each traveler will choose a path that minimizes his/her total travel time from the hotel to the peak while staying completely within the map and avoiding dangerous regions. Your task is to determine the minimum time required among all travelers to reach the peak, and count how many travelers achieve that minimum time.

The problem may require taking detours (which might involve moving left or up) if a direct monotonic path is blocked by dangerous cells.

Note on formulas: For a given traveler, if a chosen path consists of u uphill moves and d downhill moves, then its total travel time is given by:

[ T = u \cdot a_i + d \cdot b_i ]

inputFormat

The first line contains three integers n, m and k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 1000), representing the number of rows and columns of the grid, and the number of travelers respectively.

The next n lines each contain a string of length m consisting of characters '.' and '#' — a '.' denotes a safe region and a '#' denotes a dangerous region. It is guaranteed that the top left cell (0,0) and the bottom right cell (n-1,m-1) are safe, and that at least one safe route exists from the hotel to the peak.

The following k lines each contain two integers a and b (1 ≤ a, b ≤ 10⁹), where a is the time in minutes needed when moving to a higher adjacent cell (right or down) and b is the time in minutes when moving to a lower adjacent cell (left or up) for that traveler.

outputFormat

Output two integers separated by a space: the minimum time required by any traveler to reach the mountain peak and the number of travelers that achieve this minimum time.

sample

3 3 2
...
...
...
2 1
1 1

2 1