재민이의 생일

시간 제한3초메모리 제한1024 MB

요약

H×W 크기의 격자에서 정확히 N칸으로 이루어진 직사각형 중 최댓값과 최솟값의 차이가 가장 큰 것을 찾습니다. 그런 직사각형이 없으면 -1을 출력합니다.

난이도: 보통10점 중 7점
유형: 행렬, 투 포인터, 슬라이딩 윈도우
정답자: 아직 제출이 없습니다

문제

재민이의 생일을 맞아 $N$ 명의 친구가 생일 파티에 초대되었다. 재민이는 친구들을 위해 직사각형 모양의 케이크를 하나 준비했다.

케이크는 $H \times W$ 크기의 격자로 나뉘어 있으며, 총 $HW$ 개의 조각으로 이루어져 있다. 각 조각에는 단맛의 정도를 나타내는 $1$ 이상 $10^{9}$ 이하의 정수가 주어진다. 값이 클수록 더 달콤한 조각이다. $i$ 행 $j$ 열에 있는 조각 $(i,j)$ 의 단맛은 $S_{ij}$ 이다.

재민이는 친구들이 오기 전에 나누어 줄 조각을 미리 골라 두려고 한다. 고르는 조건은 다음과 같다.

정확히 $N$ 개의 조각을 선택해야 한다.
선택된 조각들은 직사각형 영역을 이루어야 한다.

조각들이 직사각형 영역을 이룬다는 것은, 다음 조건을 만족하는 정수 $s_1, e_1, s_2, e_2$ 가 존재한다는 뜻이다.

$1 \le s_1 \le e_1 \le H$
$1 \le s_2 \le e_2 \le W$
선택된 조각들은 $s_1 \le i \le e_1$ 이고 $s_2 \le j \le e_2$ 인 조각 $(i,j)$ 들의 집합과 정확히 같다.

친구들이 어느 정도의 단맛을 좋아하는지 알 수 없으므로, 재민이는 선택한 $N$ 개의 조각 중 가장 단맛이 큰 조각과 가장 단맛이 작은 조각의 단맛 차이를 최대화하려고 한다. 재민이를 도와 어떤 조각을 선택해야 하는지 구하라.

입력

첫째 줄에 케이크의 크기를 나타내는 두 정수 $H$ , $W$ 와 친구들의 수 $N$ 이 공백으로 구분되어 주어진다. ( $1 \le H,W \le 500\,000$ ; $HW \le 500\,000$ ; $1 \le N \le HW$ )

둘째 줄부터 $H$ 개의 줄에 걸쳐, 각 조각의 단맛을 나타내는 정수 $S_{i1}$ , $\cdots$ , $S_{iW}$ 가 공백으로 구분되어 주어진다. ( $1 \le S_{ij} \le 10^{9}$ )

출력

조건을 만족하도록 케이크를 자르는 것이 불가능한 경우 $-1$ 을 출력한다.

케이크를 자르는 것이 가능한 경우, 단맛 차이의 최댓값을 출력한다.

예제3

예제 1
입력
```
3 5 6
6 5 4 8 7
2 4 4 5 6
3 1 3 5 2
```
예상 출력
```
6
```
예제 2
입력
```
2 6 9
3 6 4 3 5 8
2 1 5 1 5 9
```
예상 출력
```
-1
```
예제 3
입력
```
2 3 1
17 13 84
81 22 47
```
예상 출력
```
0
```