In Zagreb, der Hauptstadt Kroatiens, wurde beschlossen, anlässlich der Austragung der IOI 2007 am Stadtrand ein großes Einkaufszentrum zu errichten. Das potenzielle Baugebiet für das Einkaufszentrum ist wie in der folgenden Abbildung dargestellt gitterförmig in $m$ Blöcke horizontal und $n$ Blöcke vertikal unterteilt.

Die Stadt Zagreb hat beschlossen, innerhalb des potenziellen Baugebiets einen rechteckigen Bereich von $a$ Blöcken horizontal mal $b$ Blöcken vertikal auszuwählen und dort das Einkaufszentrum zu bauen. Allerdings sind einige Blöcke innerhalb des potenziellen Baugebiets bereits bewohnt, sodass auf diesen Grundstücken kein Einkaufszentrum gebaut werden kann. Wenn sich innerhalb eines rechteckigen Bereichs von $a$ Blöcken horizontal mal $b$ Blöcken vertikal kein bewohnter Block befindet, kann das Einkaufszentrum gebaut werden, indem alle Blöcke innerhalb dieses rechteckigen Bereichs aufgekauft werden.

Aus finanziellen Gründen der Stadt Zagreb müssen die Kosten für den Grunderwerb so gering wie möglich gehalten werden. Um einen Haushaltsplan aufzustellen, müssen die für den Bau des Einkaufszentrums erforderlichen Grunderwerbskosten dringend berechnet werden. Daher hat die Stadt Zagreb beschlossen, dich als Auswahlkandidaten für die IOI 2007 mit der Erstellung eines entsprechenden Programms zu beauftragen.

Schreibe ein Programm, das bei gegebener Größe des potenziellen Baugebiets, der Größe des Einkaufszentrums sowie für jeden Block der Information, ob dort Menschen wohnen, und – falls dort niemand wohnt – den Kosten für den Erwerb dieses Blocks die minimalen Kosten für den Grunderwerb zum Bau des Einkaufszentrums bestimmt.

Im Folgenden wird der Block in der $i$-ten Spalte von links und der $j$-ten Zeile von oben des potenziellen Baugebiets mit $(i, j)$ bezeichnet.

Eingabe

In der ersten Zeile der Eingabedatei mall.in stehen zwei durch ein Leerzeichen getrennte ganze Zahlen $m, n$ ($1 \le m, n \le 1000$). Dies gibt an, dass das potenzielle Baugebiet $m$ Blöcke horizontal und $n$ Blöcke vertikal groß ist.

In der zweiten Zeile stehen zwei durch ein Leerzeichen getrennte ganze Zahlen $a, b$ ($1 \le a, b \le 1000$). Dies gibt an, dass das Einkaufszentrum $a$ Blöcke horizontal und $b$ Blöcke vertikal groß ist.

Die folgenden $n$ Zeilen (Zeile $3$ bis Zeile $n + 2$) enthalten Informationen über die einzelnen Blöcke innerhalb des potenziellen Baugebiets. Zeile $j + 2$ ($1 \le j \le n$) gibt die Informationen über die Blöcke in der $j$-ten Zeile von oben an und enthält $m$ durch Leerzeichen getrennte ganze Zahlen $c_{1,j}, \dots, c_{m,j}$ ($-1 \le c_{i,j} \le 100$). Wenn $c_{i,j} = -1$ ist, bedeutet dies, dass im Block $(i, j)$ Menschen wohnen. Andernfalls gibt es an, dass die Kosten für den Erwerb von Block $(i, j)$ gleich $c_{i,j}$ sind.

Beachte, dass für die zur Bewertung verwendeten Eingabedaten der Bau des Einkaufszentrums immer möglich ist.

Ausgabe

Die Ausgabe erfolgt auf die Standardausgabe. Gib die minimalen Grunderwerbskosten aus, die für den Bau des Einkaufszentrums erforderlich sind.

Beispiel

Eingabe 1

7 6
3 2
26 29 84 15 -1 1 71
45 14 38 91 62 77 35
68 -1 -1 90 63 56 70
31 2 4 74 72 41 90
100 26 21 -1 44 72 60
71 4 40 93 48 -1 50

Ausgabe 1

184

Das Baugelände des Einkaufszentrums in diesem Ein-/Ausgabebeispiel ist unten dargestellt. Ein mit $\times$ markierter Block bedeutet, dass dort bereits Menschen wohnen.

Hinweis

Achte auf die Größe der Eingabedaten. Insbesondere da iostream in C++ langsam ist, empfiehlt es sich, bei Bedarf fscanf oder Ähnliches zu verwenden.