시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 255 90 70 35.354%

문제

땅 위에 놓여있는 세로 N, 가로 M 길이의 광산에 1 × 1 광물 N × M개가 있으며, 각 광물은 고유의 강도Si, j를 가진다.


채굴기를 이용하여 이 광물들을 채굴하려고 한다. 채굴기는 공기와 맞닿아 있는 광물 하나를 골라 채굴할 수 있다. 바닥과 광물과만 맞닿아 있으면 채굴할 수 없다. 채굴기의 성능 D에 대해, 채굴기는 강도가 D 이하인 광물들만 채굴할 수 있다. 원하는 광물의 수 K 이상을 채굴할 수 있는 최소의 D를 구하여라.

입력

첫째 줄에 NMK가 주어진다. (1 ≤ N, M ≤ 1000, 0 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., N, j = 1, 2, ..., M) (1 ≤ Si, j ≤ 106)

출력

K개 이상의 광물을 채굴할 수 있는 최소의 D를 구하여라.

예제 입력 1

5 5 10
3 3 3 3 3
3 2 2 2 3
3 2 2 2 3
3 2 2 2 3
3 2 2 2 3

예제 출력 1

3

출처

Contest > 웰노운컵 > 제 1회 웰노운컵 G1번