쇼핑몰 (Mall)

크로아티아의 수도 자그레브는 IOI2007 개최에 맞추어 교외에 대형 쇼핑몰을 짓기로 했다. 쇼핑몰 건설 후보지는 아래 그림처럼 가로 m블록, 세로 n블록의 격자로 나뉘어 있다.

건설 후보지의 예 (m = 10, n = 7)

자그레브시는 건설 후보지 안에서 가로 a블록, 세로 b블록 크기의 직사각형 영역을 골라 그곳에 쇼핑몰을 짓기로 했다. 그러나 건설 후보지 안의 여러 블록에는 이미 사람이 살고 있어서 그 땅에는 쇼핑몰을 지을 수 없다. 가로 a블록, 세로 b블록 크기의 직사각형 영역 안에 사람이 사는 블록이 없으면, 그 직사각형 영역 안의 블록을 모두 사들여 쇼핑몰을 지을 수 있다.

자그레브시의 재정 사정 때문에 용지 매입에 드는 비용은 최대한 줄여야 한다. 예산안을 세우려면 쇼핑몰 건설을 위한 용지 매입에 필요한 비용을 빨리 계산해야 한다. 그래서 자그레브시는 이를 위한 프로그램 작성을 IOI2007 대표 후보인 당신에게 부탁했다.

입력으로 건설 후보지의 크기와 쇼핑몰의 크기가 주어지고, 각 블록마다 사람이 살고 있는지 여부와 사람이 살지 않으면 그 블록을 사들이는 데 필요한 비용이 주어질 때, 쇼핑몰 건설을 위한 용지 매입에 필요한 비용의 최솟값을 구하는 프로그램을 작성하라.

아래에서 건설 후보지의 왼쪽에서 i번째 열, 위에서 j번째 행의 블록을 (i, j)로 나타낸다.

입력의 첫째 줄에는 두 정수 m, n (1 ≤ m, n ≤ 1000)이 공백을 사이에 두고 주어진다. 이는 건설 후보지의 크기가 가로 m블록, 세로 n블록임을 나타낸다.

둘째 줄에는 두 정수 a, b (1 ≤ a, b ≤ 1000)가 공백을 사이에 두고 주어진다. 이는 쇼핑몰의 크기가 가로 a블록, 세로 b블록임을 나타낸다.

이어지는 n개 줄 (3번째 줄부터 n + 2번째 줄까지)에는 건설 후보지 안의 각 블록의 정보가 쓰여 있다. j + 2번째 줄 (1 ≤ j ≤ n)은 위에서 j번째 행 블록의 정보를 나타내며, m개의 정수 c1,j , . . . , cm,j (−1 ≤ ci,j ≤ 100)가 공백을 사이에 두고 주어진다. ci,j = −1이면 블록 (i, j)에 사람이 살고 있음을 나타낸다. 그렇지 않으면 블록 (i, j)를 사들이는 데 드는 비용이 ci,j임을 나타낸다.

채점에 사용하는 입력 데이터에서는 쇼핑몰 건설이 항상 가능하다.

출력은 표준 출력으로 한다. 쇼핑몰 건설을 위한 용지 매입에 필요한 비용의 최솟값을 출력하라.

이 입출력 예에서의 쇼핑몰 건설지를 그림으로 나타내면 다음과 같다. ×가 있는 블록은 이미 사람이 살고 있음을 뜻한다.