Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Некада давно, било је време програмера који нису тестирали своје кодове, време Програмера са Кариба. Ови програмери пловили су морем и сејали страх и неквалитетне програме дуж карипских острва; за собом су остављали уплакане кориснике, незавршене апликације и чланове посаде који би користили C уместо C++-а. Сваки брод који би им се супротставио, добио би флоатинг поинт ексепшн и престао би да флоат…
Популарно место за окупљање Програмера са Кариба било је Карипско острво Тортуга. Залив овог острва можемо представити бинарном матрицом димензије \(n \times m\) чије је свако поље копно (означено јединицом) или вода (означено нулом). Програмерски бродови долазе у разним дужинама и уколико је дужина неког брода \(x\), то значи да тај брод заузима тачно \(x\) узастопних поља залива, било вертикално или хоризонтално (ширина брода је тачно једно поље). Према томе, брод дужине \(x\) се може паркирати у залив ако и само ако постоји \(x\) узастопних поља у истој врсти или истој колони матрице залива при чему сва поља представљају воду и на ниједном од њих се не налази део неког другог брода. У општем случају, може постојати више начина за паркирање.
Једног дана, у залив Тортуге стигао је програмер Џек Врабац на свом броду Black Perl дужине \(a\) и решио да га упаркира. Џек зна да после њега у залив стиже програмер Барбоса на свом броду Blue Pascal дужине \(b\), као и да Барбоса највише на свету мрзи три ствари: програмера Џека, дебуг мод и недовољно места за паркирање брода. Зато је Џек одлучио да паркира свој брод тако да после његовог паркирања буде најмање могуће начина да се у залив упаркира Барбосин брод. Како је програмер Џек познат по томе што не зна да програмира, затражио је помоћ од вас и као награду неће вам хаковати рачунар.
У првом реду стандардног улаза налазе се четири природна броја \(n\), \(m\), \(a\) и \(b\), раздвојена размаком, која, редом, представљају димензије залива, дужину Џековог брода и дужину Барбосиног брода. Затим следи опис залива - у наредних \(n\) редова налази се по \(m\) карактера (без размака) од којих је сваки ‘0’ или ‘1’.
У првом и једином реду стандардног излаза исписати један природан број - најмањи могући број начина за паркирање Барбосиног брода након паркирања Џековог брода.
<div class="panel panel-default">
<div class="panel-heading">
<span class="pull-left" style="width: 48%;">Ulaz</span>
<span style="padding-left: 15px;">Izlaz</span>
</div>
<div class="panel-body">
<span class="pull-left exampleinput">
5 6 3 3<br/>
110111<br/>
000001<br/>
000001<br/>
111101<br/>
100010
</span>
<span class="exampleoutput">
2
</span>
</div>
</div><div class="panel panel-default">
<div class="panel-heading">
<span class="pull-left" style="width: 48%;">Ulaz</span>
<span style="padding-left: 15px;">Izlaz</span>
</div>
<div class="panel-body">
<span class="pull-left exampleinput">
2 5 2 5<br/>
00000<br/>
00000
</span>
<span class="exampleoutput">
0
</span>
</div>
</div>У првом тест примеру су дужине Џековог и Барбосиног брода по 3. Уколико Џек паркира свој брод тако да заузима поља (1,3)(2,3)(3,3), Барбоса ће имати само два начина за паркирање свог брода - (2,5)(3,5)(4,5) и (5,2)(5,3)(5,4) (врсте су нумерисане одозго надоле а колоне с лева удесно). Џек никако не може паркирати свој брод тако да Барбоса има мање од два начина за паркирање.
Постоје \(5\) подзадатака, у којима додатно важи: