Problem Description

Aoi, a student at JOI High School, enjoys creating digital art, and today she made a new image.

The size of this image is $H$ pixels in height and $W$ pixels in width, represented as a grid of $H \times W$ squares. Here, the pixel at the $i$-th row from the top ($1 \leq i \leq H$) and the $j$-th column from the left ($1 \leq j \leq W$) is denoted as $(i, j)$. Each pixel is painted in one color. Each color is assigned a number from 1 to 256, and the color number of pixel $(i, j)$ is $A_{i, j}$.

Aoi showed this image to her classmate Rin, but Rin disliked it because "there are too many different colors used in the image." Therefore, Aoi thought about hiding a certain area in the image to minimize the number of visible colors.

• Aoi will hide at most $S$ pixels.
• However, the hidden pixels must form a single rectangle.

Given the image data and the maximum number of pixels $S$ that can be hidden, create a program that finds the minimum number of visible colors when a certain area in the image is hidden.

Input Format

The input is given from the standard input in the following format:

$H$ $W$ $S$ $A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$ $\vdots$ $A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$

Output Format

Output the minimum number of visible colors when a certain area in the image is hidden to the standard output in one line.

Especially, if it is possible to make all pixels invisible, output $0$.

Sample Input and Output

Sample Input #1

1 10 7
5 1 2 5 2 2 5 6 6 5

Sample Output #1

2

Sample Input #2

10 10 45
1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 3 3 1 1 1
1 1 2 1 2 3 1 3 1 1
1 2 1 2 6 6 3 1 3 1
1 2 2 6 1 1 6 3 3 1
1 4 4 6 1 1 6 5 5 1
1 4 1 4 6 6 5 1 5 1
1 1 4 1 4 5 1 5 1 1
1 1 1 4 4 5 5 1 1 1
1 1 1 1 1 1 1 1 1 1

Sample Output #2

4

Sample Input #3

5 10 1
2 3 5 7 1 1 1 3 1 7
1 9 2 3 2 9 3 1 3 7
4 1 4 3 4 7 5 3 5 9
6 1 6 7 7 1 7 3 7 9
8 3 8 9 9 7 2 3 5 7

Sample Output #3

9

Sample Input #4

9 6 54
1 1 1 1 1 3
6 14 14 3 3 12
9 13 1 10 3 3
9 13 5 5 3 3
6 13 10 3 7 3
2 5 8 5 3 3
6 5 5 3 15 3
6 5 10 5 3 3
2 2 5 7 3 3

Sample Output #4

0

Sample Input #5

8 10 59
3 3 3 3 3 3 3 3 2 3
3 1 3 3 3 3 3 2 3 3
3 3 1 4 3 4 2 3 3 3
3 3 3 1 4 2 4 3 3 3
3 3 3 4 1 4 2 3 3 3
3 3 3 1 4 3 4 2 3 3
3 3 1 3 3 3 3 3 2 3
3 1 3 3 3 3 3 3 3 3

Sample Output #5

2

Notes/Hints

Constraints

• $1 \leq H \leq 1,000$.
• $1 \leq W \leq 1,000$.
• $1 \leq S \leq$.
• $1 \leq A_{i, j} \leq 256$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
• All input values are integers.

Subtasks

1. ($8$ points) $H = 1$, $W \leq 10$.
2. ($10$ points) $H \leq 10$, $W \leq 10$.
3. ($5$ points) $S = 1$.
4. ($6$ points) $A_{i, j} \leq 2$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
5. ($5$ points) $A_{i, j} \leq 4$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
6. ($13$ points) $A_{i, j} \leq 15$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
7. ($13$ points) $A_{i, j} \leq 30$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
8. ($15$ points) $A_{i, j} \leq 70$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
9. ($25$ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the scores of the subtasks that the submitted source code correctly solves.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked from the "My Score" tab in the "Submission Results".

Sample Explanation 1

For example, hiding the pixels from the 2nd to the 8th from the left, only the colors numbered $5, 6$ are visible, and the number of their types is $2$. In this case, the hidden pixels are $7$, which satisfies the condition. Also, Aoi cannot make the visible colors less than $1$ type. Therefore, output $2$. This input example satisfies the constraints of subtasks $1, 2, 6, 7, 8, 9$.

Sample Explanation 2

For example, hiding the rectangular area with the top-left pixel $(2, 1)$ and the bottom-right pixel $(7, 7)$, only the colors numbered $1, 3, 4, 5$ are visible, and the number of their types is $4$. In this case, the hidden pixels are $42$, which satisfies the condition. This explanation can be illustrated as follows: This input example satisfies the constraints of subtasks $2, 6, 7, 8, 9$.

Sample Explanation 3

Under the condition that at most $S = 1$ pixel can be hidden, Aoi can only make the colors numbered $1, 2, 3, \ldots, 9$ visible. Therefore, output $9$. This input example satisfies the constraints of subtasks $2, 3, 6, 7, 8, 9$.

Sample Explanation 4

It is possible to hide all $54$ pixels, making no pixels visible. Therefore, output $0$. This input example satisfies the constraints of subtasks $2, 6, 7, 8, 9$.

Sample Explanation 5

For example, hiding the rectangular area with the top-left pixel $(3, 1)$ and the bottom-right pixel $(10, 7)$, only the colors numbered $1, 3$ are visible, and the number of their types is $2$. In this case, the hidden pixels are $56$, which satisfies the condition. This explanation can be illustrated as follows: This input example satisfies the constraints of subtasks $2, 5, 6, 7, 8, 9$.

见题面 Input 部分

见题面 Output 部分