This page is still under construction.

Parts of this page are still being built. What you see may change.

Digital Art

Time limit1sMemory limit1024 MB

Summary
Given an H by W grid of color numbers, cover one rectangle of at most S pixels to minimize the number of distinct colors still visible.
Level

Hard8 of 10

Topics
Sliding window, Two pointers, Prefix sum, Implementation
Solved
No attempts yet

Problem

Aoi, a student at JOI High School, makes digital art as a hobby, and today she made a new image.

The image is H pixels tall and W pixels wide, represented as an H × W grid. The pixel in the i-th row from the top (1 ≦ i ≦ H) and the j-th column from the left (1 ≦ j ≦ W) is written (i, j). Each pixel is painted with one color. Each color has a number from 1 to 256, and the color number of pixel (i, j) is Ai, j.

Aoi showed this image to her classmate Rin, but Rin did not like it, saying "the image uses too many colors." So Aoi wondered whether she could cover some region of the image as follows to make the number of visible colors as small as possible.

  • Aoi chooses at most S pixels and covers them.
  • The region of covered pixels must be a single rectangle.

Given the image data and the upper bound S on the number of covered pixels, write a program to find the minimum possible number of visible colors when some region of the image is covered.

Input

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

H W S
A1, 1   A1, 2   …   A1, W
A2, 1   A2, 2   …   A2, W
:
AH, 1   AH, 2   …   AH, W

Output

On standard output, print in one line the minimum possible number of visible colors when some region of the image is covered.

In particular, if it is possible to make no pixel visible, print 0.

Constraints

  • 1 ≦ H ≦ 1 000.
  • 1 ≦ W ≦ 1 000.
  • 1 ≦ S ≦ HW.
  • 1 ≦ Ai, j ≦ 256 (1 ≦ i ≦ H, 1 ≦ j ≦ W).
  • All given values are integers.

Examples5

  1. Example 1

    Input
    1 10 7
5 1 2 5 2 2 5 6 6 5
    Expected output
    2

  2. Example 2

    Input
    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
    Expected output
    4

  3. Example 3

    Input
    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
    Expected output
    9

  4. Example 4

    Input
    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
    Expected output
    0

  5. Example 5

    Input
    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
    Expected output
    2