프로그램 명: ioi_qualiv
제한시간: 10 초

알버타시에서는 도시가 직사각형 격자모양의 블록으로 설계되어 있다. 행으로 0 .. R-1 , 열로는 0..C-1 로 블록은 나누어져 있다.

각 블록은 삶의 질은 1 에서 R*C 사이의 유일한 수로 quality rank 를 나타낸다. 1 은 가장 좋고 , R*C 가 가장 나쁘다.

도시 계획과에서는 H * W 의 영역에서 삶의 질의 중간 값을 조사해서 이 중 가장 좋은 것을 찾기를 원한다.

H 와 W 는 홀수이고 각각은 R,C 를 초과하지 않는다.

홀수개의 랭크에서 중간 랭크 m 은 m 보다 더 좋은 랭크의 수가 m 보다 더 나쁜 랭크의 수와 같은 것으로 정의 한다.

제한 시간은 10 초이다.

Implementation Details(더블릿에서는 불 필요)▶

입력

입력으로 R,C,H,W 가 주어지고 , 다음 각 블럭의 랭크가 주어진다. R,C 는 3000 을 넘지 않는다.

출력

가장 좋은(수로는 가장 작은) 중간 값을 출력한다.

입출력 예

입력






 5   5   3   3 



 
5  11   12   16   25 





 17  18   2   7   10 





 4  23   20   3   1 





 24  21   19   14   9 





 6  22   8   13   15 





출력

9

입력

2 6 1 5 
6 1 2 11 7  5
9 3 4 10 12  8

출력

5

출처:ioi 2010 day1 3
[질/답] [제출 현황] [푼 후(2)]
[ 채 점 ] [홈으로]  [뒤 로]