Kroatian pääkaupungissa Zagrebissa on päätetty rakentaa esikaupunkialueelle suuri ostoskeskus IOI 2007 -kilpailun järjestämisen yhteydessä. Ostoskeskuksen rakennuspaikkaehdokas on jaettu alla olevan kuvan mukaisesti ruudukkoon, jossa on vaakasuunnassa $m$ korttelia ja pystysuunnassa $n$ korttelia.

Zagrebin kaupunki on päättänyt valita rakennuspaikkaehdokkaan sisältä suorakulmion muotoisen alueen, jonka koko on vaakasuunnassa $a$ korttelia ja pystysuunnassa $b$ korttelia, ja rakentaa ostoskeskuksen siihen. Joissakin rakennuspaikkaehdokkaan kortteleissa asuu kuitenkin jo ihmisiä, eikä niille tonteille voi rakentaa ostoskeskusta. Jos vaakasuunnassa $a$ korttelin ja pystysuunnassa $b$ korttelin kokoisen suorakulmion muotoisen alueen sisällä ei ole yhtään asuttua korttelia, ostoskeskus voidaan rakentaa lunastamalla kaikki kyseisen suorakulmion muotoisen alueen sisällä olevat korttelit.

Zagrebin kaupungin taloudellisista syistä maanlunastukseen kuluva kustannus on pidettävä mahdollisimman pienenä. Budjettiesityksen laatimista varten on kiireellisesti laskettava ostoskeskuksen rakentamiseen tarvittavien maanlunastusten kustannus. Niinpä Zagrebin kaupunki on päättänyt pyytää sinua, IOI 2007 -edustajaehdokasta, laatimaan ohjelman tätä varten.

Kirjoita ohjelma, joka saa syötteenä rakennuspaikkaehdokkaan koon, ostoskeskuksen koon sekä kunkin korttelin osalta tiedon siitä, asuuko siellä ihmisiä, ja jos siellä ei asu ketään, kyseisen korttelin lunastamiseen tarvittavan kustannuksen, ja etsii pienimmän mahdollisen maanlunastuskustannuksen ostoskeskuksen rakentamiseksi.

Jatkossa rakennuspaikkaehdokkaan vasemmalta $i$-nnessä sarakkeessa ja ylhäältä $j$-nnessä rivissä olevaa korttelia merkitään $(i, j)$:llä.

Syöte

Syötetiedoston mall.in ensimmäisellä rivillä on kaksi välilyönnillä erotettua kokonaislukua $m, n$ ($1 \le m, n \le 1000$). Tämä tarkoittaa, että rakennuspaikkaehdokkaan koko on vaakasuunnassa $m$ korttelia ja pystysuunnassa $n$ korttelia.

Toisella rivillä on kaksi välilyönnillä erotettua kokonaislukua $a, b$ ($1 \le a, b \le 1000$). Tämä tarkoittaa, että ostoskeskuksen koko on vaakasuunnassa $a$ korttelia ja pystysuunnassa $b$ korttelia.

Seuraavilla $n$ rivillä (riviltä $3$ riville $n + 2$) on tiedot rakennuspaikkaehdokkaan kustakin korttelista. Rivi $j + 2$ ($1 \le j \le n$) kuvaa ylhäältä $j$-nnen rivin kortteleiden tietoja, ja sillä on $m$ välilyönnein erotettua kokonaislukua $c_{1,j}, \dots, c_{m,j}$ ($-1 \le c_{i,j} \le 100$). Kun $c_{i,j} = -1$, se tarkoittaa, että korttelissa $(i, j)$ asuu ihmisiä. Muussa tapauksessa se tarkoittaa, että korttelin $(i, j)$ lunastamiseen kuluva kustannus on $c_{i,j}$.

Huomaa, että arvostelussa käytettävillä syötetiedoilla ostoskeskuksen rakentaminen on aina mahdollista.

Tuloste

Tuloste tulee kirjoittaa standarditulosteeseen. Tulosta ostoskeskuksen rakentamiseen tarvittavan maanlunastuskustannuksen pienin mahdollinen arvo.

Esimerkki

Syöte 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

Tuloste 1

184

Tämän syöte- ja tulosteesimerkin mukainen ostoskeskuksen rakennuspaikka on havainnollistettu alla olevassa kuvassa. Merkillä $\times$ merkitty kortteli tarkoittaa, että siellä asuu jo ihmisiä.

Huomautus

Kiinnitä huomiota syötetietojen kokoon. Erityisesti C++:n iostream on hidas, joten tarvittaessa kannattaa käyttää fscanf-funktiota tai vastaavaa.