문제
여러분은 심시티의 시민이다. 최근 시장님이 주거지역을 새로 확정 지었고, 공사가 막 시작되었다. 주거지역의 적당한 구역을 사서, 시간이 지나 오르게 될 땅값으로 여러분은 새로운 노트북도 사고, 메이플 캐시템을 구매하는 등 걱정 없이 놀고 싶어 한다.
주거지역은 m*n 짜리 직사각형 격자로 되어 있고, 여러분은 이 중 a*b 짜리 지역을 구매하고 싶어 한다(땅은 정확히 정사각형 모양으로 나뉘어 있다.).
주거지역의 모든 칸은 시간이 지남에 따라 땅값이 동일하게 올라간다고 한다. 이익금을 최대로 하기 위해 여러분은 a*b 크기의 지역 중 현재 땅값이 가장 낮은 지역을 구매하려고 한다. 부동산 주인은 각 정사각형 지역의 평균 땅값이 적힌 지도를 주었다. 어떻게 하면 비용을 최소화할 수 있을까?
입력
첫째 줄에 네 개의 정수 m, n, a, b가 차례대로 입력된다(3<=m<=1000, 3<=n<=1000, 1<=a<=m, 1<=b<=n).
이후 m개의 줄에 n개의 정수가 입력되는데, 이는 해당 칸의 땅값을 나타낸다. 땅값의 범위는 100 이하의 자연수이다.
출력
첫 번째 줄에 최소 비용을 출력한다.
예제
5 5 2 2
1 2 3 4 5
5 4 1 2 5
2 4 1 1 5
4 5 6 4 4
3 4 5 2 1
5
로그인해야 코드를 작성할 수 있어요.