I Zagreb, hovedstaden i Kroatia, har man besluttet å bygge et stort kjøpesenter i forstedene i forbindelse med gjennomføringen av IOI 2007. Kandidatområdet for byggingen av kjøpesenteret er delt inn i et rutenett med $m$ kvartaler horisontalt og $n$ kvartaler vertikalt, som vist i figuren nedenfor.

Zagreb kommune har besluttet å velge ut et rektangulært område på $a$ kvartaler horisontalt ganger $b$ kvartaler vertikalt innenfor kandidatområdet og bygge kjøpesenteret der. Imidlertid bor det allerede mennesker i noen av kvartalene innenfor kandidatområdet, og det er ikke mulig å bygge kjøpesenteret på disse tomtene. Hvis det ikke er noen bebodde kvartaler innenfor et rektangulært område på $a$ kvartaler horisontalt ganger $b$ kvartaler vertikalt, kan kjøpesenteret bygges ved å kjøpe opp alle kvartalene innenfor det rektangulære området.

Av økonomiske årsaker for Zagreb kommune må kostnadene ved tomtekjøp holdes så lave som mulig. For å utarbeide et budsjettforslag er det nødvendig å raskt beregne kostnadene som kreves for tomtekjøp til byggingen av kjøpesenteret. Derfor har Zagreb kommune bestemt seg for å be deg, som er en representantkandidat til IOI 2007, om å lage et program for dette formålet.

Skriv et program som, gitt størrelsen på kandidatområdet, størrelsen på kjøpesenteret samt informasjon for hvert kvartal om hvorvidt det bor mennesker der, og – hvis ingen bor der – kostnaden som kreves for å kjøpe dette kvartalet, finner den minste kostnaden som kreves for tomtekjøp til å bygge kjøpesenteret.

I det følgende betegnes kvartalet i den $i$-te kolonnen fra venstre og den $j$-te raden ovenfra i kandidatområdet med $(i, j)$.

Inndata

Den første linjen i inndatafilen mall.in inneholder to heltall $m, n$ ($1 \le m, n \le 1000$) atskilt med et mellomrom. Dette angir at størrelsen på kandidatområdet er $m$ kvartaler horisontalt og $n$ kvartaler vertikalt.

Den andre linjen inneholder to heltall $a, b$ ($1 \le a, b \le 1000$) atskilt med et mellomrom. Dette angir at størrelsen på kjøpesenteret er $a$ kvartaler horisontalt og $b$ kvartaler vertikalt.

De påfølgende $n$ linjene (fra linje $3$ til linje $n + 2$) inneholder informasjon om hvert kvartal innenfor kandidatområdet. Linje $j + 2$ ($1 \le j \le n$) representerer informasjonen om kvartalene i den $j$-te raden ovenfra, og inneholder $m$ heltall $c_{1,j}, \dots, c_{m,j}$ ($-1 \le c_{i,j} \le 100$) atskilt med mellomrom. Når $c_{i,j} = -1$, betyr det at det bor mennesker i kvartal $(i, j)$. Ellers betyr det at kostnaden for å kjøpe kvartal $(i, j)$ er $c_{i,j}$.

Merk at for inndataene som brukes til bedømming, er det alltid mulig å bygge kjøpesenteret.

Utdata

Utdata skal skrives til standard utdata. Skriv ut den minste kostnaden som kreves for tomtekjøp for å bygge kjøpesenteret.

Eksempel

Inndata 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

Utdata 1

184

Byggetomten for kjøpesenteret i dette eksempelet på inndata og utdata er illustrert nedenfor. Et kvartal merket med $\times$ betyr at det allerede bor mennesker der.

Merk

Vær oppmerksom på størrelsen på inndataene. Spesielt siden iostream i C++ er treg, anbefales det å bruke fscanf eller lignende ved behov.