Description

Mr. Robinson has a pet monkey named Duoduo. One day, while they were taking a walk along a country road, they suddenly noticed a small note posted on a roadside sign: "Welcome to taste my peanuts for free! — Bear."

Both Mr. Robinson and Duoduo were delighted because peanuts are their favorite. Behind the sign, there was indeed a peanut field with peanut plants neatly arranged in a rectangular grid (as shown in Figure 1). With experience, Duoduo could tell at a glance how many peanuts were under each plant. To train Duoduo's arithmetic skills, Mr. Robinson said: "First, find the plant with the most peanuts and pick them; then find the plant with the most peanuts among the remaining ones and pick them; and so on. However, you must return to the roadside within the time limit I set."

Assume that in each unit of time, Duoduo can perform one of the following four actions:

1) Jump from the roadside to the closest row (i.e., the first row) of a peanut plant;

2) Jump from one plant to another adjacent plant in the front, back, left, or right;

3) Pick the peanuts under a plant;

4) Jump back to the roadside from the closest row (i.e., the first row) of a peanut plant.

Now, given the size of the peanut field and the distribution of peanuts, determine the maximum number of peanuts Duoduo can pick within the time limit. Note that only some plants may have peanuts underneath, and assume the number of peanuts under these plants varies.

For example, in the peanut field shown in Figure 2, only the plants located at (2, 5), (3, 7), (4, 2), (5, 4) have peanuts, with quantities of 13, 7, 15, 9, respectively. Following the illustrated route, Duoduo can pick a maximum of 37 peanuts within 21 units of time.

Input Format

The first line of input contains three integers, M, N, and K, separated by spaces; representing the size of the peanut field as M * N (1 <= M, N <= 20) and the time limit for Duoduo to pick peanuts as K (0 <= K <= 1000) units of time. The next M lines each contain N non-negative integers, also separated by spaces; the j-th integer in the i + 1-th line, Pij (0 <= Pij <= 500), indicates the number of peanuts under the plant at (i, j), where 0 means no peanuts under that plant.

Output Format

The output consists of a single line containing one integer, which is the maximum number of peanuts Duoduo can pick within the given time limit.

```input1 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 ``` ```output1 37 ``` ## Translation

NOIP2004-J2

(Note: Since the original text only contains "NOIP2004-J2" which appears to be a competition identifier/code, I've kept it unchanged in the translation as it's likely an acronym for "National Olympiad in Informatics in Provinces 2004 - Junior Level 2" or similar competition designation. No additional context was provided for further translation.)