cho.sh

삶의 질

아직 제출이 없습니다시간 제한5초메모리 제한256 MB

문제

Alberta 시는 직사각형 격자 모양의 블록으로 설계되어 있다. 행 번호는 가장 북쪽 00번부터 가장 남쪽 R−1R-1번까지, 열 번호는 가장 서쪽 00번부터 가장 동쪽 C−1C-1번까지 붙는다.

각 블록의 삶의 질은 11부터 R×CR \times C까지의 서로 다른 수 하나로 나타내고, 이 수를 quality rank라고 한다. quality rank가 11인 블록의 삶의 질이 가장 좋고, R×CR \times C인 블록이 가장 나쁘다.

홍준이는 격자 안에 완전히 들어가는 H×WH \times W 영역만 살펴본다. HH와 WW는 홀수이고, 1≤H≤R1 \le H \le R, 1≤W≤C1 \le W \le C를 만족한다. 홀수 개의 quality rank 중에서 중간값 mm은 mm보다 좋은 랭크의 개수와 mm보다 나쁜 랭크의 개수가 같은 값으로 정의한다.

H×WH \times W 영역마다 quality rank의 중간값이 하나씩 정해진다. 그 중간값 중에서 삶의 질이 가장 좋은 값, 즉 가장 작은 값을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 정수 RR, CC, HH, WW가 공백으로 구분되어 주어진다. RR과 CC는 도시의 행과 열의 개수이고, HH와 WW는 홍준이가 정한 영역의 행과 열의 개수이다. HH와 WW는 홀수이며 1≤H≤R1 \le H \le R, 1≤W≤C1 \le W \le C이다.

다음 RR개의 줄에는 각각 CC개의 정수가 주어진다. ii번째 줄의 jj번째 수는 행 번호 i−1i-1, 열 번호 j−1j-1인 블록의 quality rank이다. 격자에 적힌 R×CR \times C개의 수는 11부터 R×CR \times C까지의 정수가 한 번씩 나타난 것이다.

출력

첫째 줄에 H×WH \times W 영역의 중간값 중 가장 작은 값을 출력한다.