Alberta 시에서는 도시가 직사각형 격자 모양의 블록으로 설계되어 있다.

블록은 가장 북쪽 0번부터 가장 남쪽 R-1번까지(행의 번호), 가장 서쪽 0번부터 가장 동쪽 C-1번까지로(열의 번호) 나누어져 있다.

각 블록에서 삶의 질은 1 부터 R×C 까지의 유일한 정수로 표현되며, 이를 quality rank라 한다.

1로 표현된 삶의 질이 가장 좋은 quality rank이고, R×C은 가장 나쁜 quality rank이다.

홍준이는 H × W (1 ≤ H ≤ R, 1 ≤ W ≤ C)의 영역에서 quality rank의 중간값 중 가장 질이 높은(수의 크기는 가장 작은) 값을 찾으려고 한다.

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

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

홍준이를 도와 H×W의 크기를 가지는 영역들 중에서, quality rank의 중간값 중 가장 질이 높은 값을 찾는 프로그램을 작성하시오.

삶의 질 ( Quality of Living ) timer 5s memory 256MB

삶의 질 ( Quality of Living ) 5s 256MB