Хорватияның астанасы Загребте IOI 2007 олимпиадасының өткізілуіне орай қала шетінде ірі сауда орталығын салу туралы шешім қабылданды. Сауда орталығын салуға үміткер жер учаскесі төмендегі суретте көрсетілгендей көлденеңінен $m$ блок, тігінен $n$ блок болатын тор түрінде бөлінген.

Загреб қаласы үміткер учаскенің ішінен көлденеңінен $a$ блок, тігінен $b$ блок болатын тіктөртбұрышты аймақты таңдап, сол жерге сауда орталығын салуды ұйғарды. Алайда үміткер учаске ішіндегі кейбір блоктарда қазірдің өзінде адамдар тұрып жатыр, сондықтан ол жерлерге сауда орталығын салу мүмкін емес. Егер көлденеңінен $a$ блок, тігінен $b$ блок болатын тіктөртбұрышты аймақтың ішінде адамдар тұратын блок болмаса, сол тіктөртбұрышты аймақ ішіндегі барлық блоктарды сатып алу арқылы сауда орталығын салуға болады.

Загреб қаласының қаржылық себептеріне байланысты жерді сатып алуға кететін шығын мүмкіндігінше аз болуы керек. Бюджет жоспарын жасау үшін сауда орталығын салуға арналған жерді сатып алуға қажетті шығынды шұғыл түрде есептеу қажет. Сондықтан Загреб қаласы осы мақсаттағы программаны жазуды IOI 2007 құрамасына үміткер ретінде сізге тапсыруды жөн көрді.

Кіріс деректері ретінде үміткер учаскенің өлшемі мен сауда орталығының өлшемі, сондай-ақ әрбір блок үшін онда адамдар тұратыны немесе тұрмайтыны туралы ақпарат және егер адамдар тұрмаса, сол блокты сатып алуға қажетті шығын берілгенде, сауда орталығын салу үшін жерді сатып алуға қажетті ең аз шығынды табатын программа жазыңыз.

Төменде үміткер учаскенің сол жағынан санағанда $i$-бағандағы, жоғарыدان санағанда $j$-жолдағы блогы $(i, j)$ деп белгіленеді.

Енгізу

mall.in енгізу файлының 1-жолында бос орын арқылы бөлінген екі бүтін сан $m, n$ ($1 \le m, n \le 1000$) жазылған. Бұл үміткер учаскенің өлшемі көлденеңінен $m$ блок, тігінен $n$ блок екенін білдіреді.

2-жолда бос орын арқылы бөлінген екі бүтін сан $a, b$ ($1 \le a, b \le 1000$) жазылған. Бұл сауда орталығының өлшемі көлденеңінен $a$ блок, тігінен $b$ блок екенін білдіреді.

Келесі $n$ жолда ($3$-жолдан $n + 2$-жолға дейін) үміткер учаске ішіндегі әрбір блоктың ақпараты жазылған. $j + 2$-жол ($1 \le j \le n$) жоғарыдан санағанда $j$-жолдағы блоктардың ақпаратын білдіреді және онда бос орындармен бөлінген $m$ бүтін сан $c_{1,j}, \dots, c_{m,j}$ ($-1 \le c_{i,j} \le 100$) жазылған. $c_{i,j} = -1$ болғанда, бұл $(i, j)$ блогында адамдар тұратынын білдіреді. Әйтпесе, бұл $(i, j)$ блогын сатып алуға кететін шығын $c_{i,j}$ екенін білдіреді.

Айта кетейік, бағалау үшін қолданылатын енгізу деректерінде сауда орталығын салу әрқашан мүмкін болады.

Шығару

Шығаруды стандартты шығару ағынына орындау керек. Сауда орталығын салу үшін жерді сатып алуға қажетті шығынның ең кіші мәнін шығарыңыз.

Мысал

Енгізу 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

Шығару 1

184

Осы енгізу және шығару мысалындағы сауда орталығы салынатын жерді сызба түрінде көрсетсек, төмендегідей болады. $\times$ белгісі бар блок онда қазірдің өзінде адамдар тұрып жатқанын білдіреді.

Ескерту

Енгізу деректерінің көлеміне назар аударыңыз. Атап айтқанда, C++ тіліндегі iostream баяу жұмыс істейтіндіктен, қажеттілігіне қарай fscanf және т.б. қолданған жөн.