Description

Mr. Robinson has a pet monkey named Duoduo. One day, while they were walking 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 by the roadside, with peanut plants arranged neatly in a rectangular grid (as shown in Figure 1). Experienced 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. But you must return to the roadside within the time limit I set."

We assume that Duoduo can perform one of the following four actions in each unit of time:

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 (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 are all distinct.

For example, in the peanut field shown in Figure 2, only the plants at (2, 5), (3, 7), (4, 2), (5, 4) have peanuts, with counts of 13, 7, 15, 9, respectively. Following the route illustrated, 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, indicating 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), represents the number of peanuts under the plant at (i, j), where 0 means the plant has no peanuts.

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 ``` ## Source

NOIP2004-J2