재민이의 생일

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

요약

H×W 격자에서 정확히 N개의 칸으로 이루어진 직사각형을 골라, 그 안 최댓값과 최솟값의 차이를 최대로 만듭니다.

난이도: 어려움10점 중 8점
유형: 배열, 슬라이딩 윈도우, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

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

재민이가 준비한 케이크는 $H\times W$ 크기의 격자 모양으로 나뉘어, 총 $HW$ 개의 조각들로 이루어져 있습니다. 각 조각은 단맛의 정도에 따라 $1$ 이상 $10^{9}$ 이하의 정수 값이 주어집니다. 이 값이 클 수록 더 달콤한 조각임을 의미합니다. $i$ 행 $j$ 열에 위치한 조각 $(i,j)$ 는 $S\_{ij}$ 만큼의 단맛을 가집니다.

재민이는 친구들이 오기 전에, 친구들에게 나누어 줄 조각들을 다음 조건을 만족하도록 골라 놓으려고 합니다.

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

어떤 조각들이 직사각형 영역을 이룬다는 것은, 다음 조건을 만족하는 $4$ 개의 정수 $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
```