15573번 - 채굴

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

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

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

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