Aventuras, Caminhadas e Montanhas (ACM) is a park known around the world for its vast mountain range. Recently, an infrastructure of cable cars has been built so that locomotion throughout the park becomes easier. The cable car stations are distributed in a rectangular network consisting of N rows and M columns, and the fee to go from one station to any of the others is D dollars.

There are also several hiking trails along the park, for those who appreciate walking in natural environments. The trails connect every horizontally or vertically adjacent station (but not diagonally adjacent ones). Alfredo and his family are visiting the park this summer vacation, and they wish to visit all of the stations in the park.

However, they consider the charged fee as overtly high. Therefore, they plan to mix walking on foot with the use of the cable cars. The route may begin on any of the cable car stations. Alfredo does not do a lot of physical exercise, and for that reason he wishes to only walk in downward slopes. The effort of a walk is proportional to the slope of the trail, that is, walking from a station with a height of H₁ to another with a height of H₂ represents an effort of (H₂ – H₁) calories.

As there are many possibilities for such routes, Alfredo asked his son João to determine the optimal route. João, in turn, asked his friend in Campinas, who was studying for the ICPC, to determine the minimal cost and effort of a visit to the ACM park.

Input

The input contains several test cases. The first line of a test case contains three integers N, M, D (1 ≤ N, M, D ≤ 15).

Each of the next N lines contains M integers. The i^th integer in the j^th line, H_ij, is the height of the i^th station on the j^th line of the cable car network (H_ij ≤ 100). The last test case is followed by one line with three zeros.

Output

For each test case, print a line with two integers, separated by spaces. The first corresponds to the minimal cost of the visit to the park, in dollars. The second represents the effort of the route that has minimal cost.

If there is more than one such route, choose the one with the least effort.

Example

Input:
2 2 1
1 2
4 3
3 3 7
1 2 1
4 5 3
1 2 1
0 0 0

Output:
0 3
21 8