P1086 [NOIP 2004 Junior] Peanut Picking

Mr. Robinson has a pet monkey named Dodo. One day, while they were walking along a country road, they found a small note on a roadside sign: “Welcome to taste my peanuts for free! — Xiong.” They were happy because peanuts are their favorite. Behind the sign, there is indeed a peanut field by the roadside, where peanut plants are arranged in a rectangular grid (see Figure 1). Experienced Dodo can tell how many peanuts are under each plant at a glance. To train Dodo’s arithmetic, Mr. Robinson says: “First find the plant with the most peanuts and pick its peanuts; then among the remaining plants, find the one with the most peanuts and pick it; and so on. But you must return to the roadside within the time limit I set.”  We assume that in each unit of time, Dodo can do exactly one of the following four actions: 1) Jump from the roadside to some peanut plant in the first row (i.e., the row closest to the roadside). 2) Jump from one plant to another plant adjacent to it in the up, down, left, or right direction. 3) Pick the peanuts under the current plant. 4) Jump from some plant in the first row back to the roadside. Given the size of the peanut field and the distribution of peanuts, compute the maximum number of peanuts Dodo can pick within the time limit. Note that only some plants may have peanuts under them. Assume that the numbers of peanuts on those plants are pairwise 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, in quantities $13, 7, 15, 9$, respectively. Along the illustrated route, Dodo can pick at most $37$ peanuts within $21$ units of time. **Note: You may not return to the roadside during the picking process.**

The first line contains three integers $M, N, K$, separated by spaces, indicating that the field size is $M \times N$ and the time limit is $K$ units. The next $M$ lines each contain $N$ non-negative integers, also separated by spaces. In the $(i + 1)$-th line, the $j$-th integer $P_{i,j}$ denotes the number of peanuts under plant $(i, j)$; $0$ means that plant has no peanuts.

Output a single integer: the maximum number of peanuts Dodo can pick within the time limit.

NOIP 2004 Junior, Problem 2. Constraints: For $100\%$ of the testdata, $1 \le M, N \le 20$, $0 \le K \le 1000$, $0 \le P_{i,j} \le 500$. Translated by ChatGPT 5