재민이의 생일

재민이의 생일을 맞아 $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$을 출력합니다.

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