Í Zagreb, höfuðborg Króatíu, hefur verið ákveðið að byggja stóra verslunarmiðstöð í úthverfi borgarinnar í tengslum við hald IOI 2007. Svæðið sem kemur til greina fyrir byggingu verslunarmiðstöðvarinnar er skipt niður í grind með $m$ reitum lárétt og $n$ reitum lóðrétt, eins og sýnt er á myndinni hér að neðan.

Borgaryfirvöld í Zagreb hafa ákveðið að velja rétthyrnt svæði af stærð $a$ reitir lárétt sinnum $b$ reitir lóðrétt innan mögulega byggingarsvæðisins og reisa verslunarmiðstöðina þar. Hins vegar býr nú þegar fólk í nokkrum reitum innan svæðisins og ekki er hægt að byggja verslunarmiðstöðina á því landi. Ef enginn reitur þar sem fólk býr er innan rétthyrnds svæðis af stærð $a$ reitir lárétt sinnum $b$ reitir lóðrétt, er hægt að byggja verslunarmiðstöðina með því að kaupa alla reitina innan þess rétthyrnda svæðis.

Af fjárhagsástæðum borgarinnar Zagreb þarf kostnaður við landakaup að vera eins lítill og mögulegt er. Til þess að gera fjárhagsáætlun þarf að reikna út í flýti þann kostnað sem þarf til landakaupa vegna byggingar verslunarmiðstöðvarinnar. Því ákvað Zagreb-borg að biðja þig, sem ert í hópi kandídata fyrir IOI 2007, að skrifa forrit í þessum tilgangi.

Skrifið forrit sem, miðað við stærð mögulega byggingarsvæðisins, stærð verslunarmiðstöðvarinnar og fyrir hvern reit upplýsingar um hvort fólk búi þar og, ef enginn býr þar, kostnaðinn við að kaupa þann reit, finnur lágmarkskostnað við landakaup til að byggja verslunarmiðstöðina.

Hér á eftir er reiturinn í $i$-ta dálki frá vinstri og $j$-tu röð að ofan á mögulega byggingarsvæðinu táknaður með $(i, j)$.

Inntak

Fyrsta línan í inntaksskránni mall.in inniheldur tvær heiltölur $m, n$ ($1 \le m, n \le 1000$) aðskildar með bili. Þetta gefur til kynna að stærð mögulega byggingarsvæðisins sé $m$ reitir lárétt og $n$ reitir lóðrétt.

Önnur línan inniheldur tvær heiltölur $a, b$ ($1 \le a, b \le 1000$) aðskildar með bili. Þetta gefur til kynna að stærð verslunarmiðstöðvarinnar sé $a$ reitir lárétt og $b$ reitir lóðrétt.

Næstu $n$ línur (frá línu $3$ til línu $n + 2$) innihalda upplýsingar um hvern reit innan mögulega byggingarsvæðisins. Lína $j + 2$ ($1 \le j \le n$) táknar upplýsingar um reitina í $j$-tu röð að ofan og inniheldur $m$ heiltölur $c_{1,j}, \dots, c_{m,j}$ ($-1 \le c_{i,j} \le 100$) aðskildar með bilum. Þegar $c_{i,j} = -1$ táknar það að fólk búi í reit $(i, j)$. Annars táknar það að kostnaðurinn við að kaupa reit $(i, j)$ sé $c_{i,j}$.

Athugið að fyrir þau inntaksgögn sem notuð eru við yfirferð er alltaf mögulegt að byggja verslunarmiðstöðina.

Úttak

Úttakið skal skrifa á staðalúttak. Skrifið út lágmarkskostnaðinn sem þarf til landakaupa vegna byggingar verslunarmiðstöðvarinnar.

Dæmi

Inntak 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

Úttak 1

184

Byggingarstaður verslunarmiðstöðvarinnar í þessu inntaks- og úttaksdæmi er sýndur á myndinni hér að neðan. Reitur merktur með $\times$ þýðir að þar búi nú þegar fólk.

Athugasemd

Gætið að stærð inntaksgagnanna. Sér í lagi þar sem iostream í C++ er hægvirkt er ráðlegt að nota fscanf eða þess háttar eftir þörfum.