디지털 아트 (Digital Art)

JOI 고등학교 학생인 아오이는 디지털 아트 제작을 취미로 삼고 있으며, 오늘도 새로운 이미지를 만들었다.

이 이미지의 크기는 세로 H 픽셀, 가로 W 픽셀이며, H × W 격자 형태로 표현된다. 위에서 i번째 행 (1 ≦ i ≦ H), 왼쪽에서 j번째 열 (1 ≦ j ≦ W)의 픽셀을 (i, j)로 나타낸다. 각 픽셀은 하나의 색으로 칠해져 있다. 각 색에는 1부터 256까지의 번호가 붙어 있으며, 픽셀 (i, j)의 색 번호는 Ai, j이다.

아오이는 이 이미지를 같은 반 친구인 린에게 보여주었지만, 린은 "이미지에 쓰인 색의 종류가 너무 많다"는 이유로 마음에 들어 하지 않았다. 그래서 아오이는 다음과 같이 이미지의 어떤 영역을 가려서 보이는 색의 종류를 최대한 줄일 수 없을지 생각했다.

• 아오이는 S개 이하의 픽셀을 골라 가린다.
• 단, 가리는 픽셀의 영역은 하나의 직사각형으로 나타내어져야 한다.

이미지의 데이터와 가릴 픽셀 개수의 상한 S가 주어졌을 때, 이미지의 어떤 영역을 가렸을 때 보이는 색의 종류 수로 가능한 최솟값을 구하는 프로그램을 작성하시오.

입력은 다음 형식으로 표준 입력에서 주어진다.

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

표준 출력에, 이미지의 어떤 영역을 가렸을 때 보이는 색의 종류 수로 가능한 최솟값을 1행으로 출력하시오.

특히, 보이는 픽셀이 하나도 없는 상태로 만들 수 있는 경우에는 0을 출력하시오.

• 1 ≦ H ≦ 1 000.
• 1 ≦ W ≦ 1 000.
• 1 ≦ S ≦ HW.
• 1 ≦ Ai, j ≦ 256 (1 ≦ i ≦ H, 1 ≦ j ≦ W).
• 입력되는 값은 모두 정수이다.