Fișierul intrare/ieșire	biscuit.in, biscuit.out	Sursă	ad-hoc
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.5 sec	Limită de memorie	600 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Biscuit

Jocul Biscuit se desfășoară pe un caroiaj dreptunghiular cu M linii și N coloane de puncte. Pe rând, doi jucători trasează segmente între două puncte vecine pe orizontală sau pe verticală. Jucătorul care închide un pătrat (de latură 1) primește un punct și mai mută o dată. Când toate segmentele au fost trasate, câștigă jucătorul care a închis mai multe pătrate.

Dându-se o tablă pe care s-au făcut deja niște mutări, să se determine câte pătrate poate închide jucătorul care este la mutare.

Date de intrare

Fișierul de intrare biscuit.in conține, pe prima linie, numerele M și N.

Pe următoarele M linii sunt descrise segmentele orizontale. Fiecare linie conține N_-1 caractere. Al _j_-lea caracter de pe linia _i este 1 sau 0 după cum al j_-lea segment orizontal de pe linia _i a fost trasat sau nu.

Pe ultimele M_-1 linii sunt descrise segmentele verticale. Fiecare linie conține _N caractere. Al j_-lea caracter de pe linia _i este 1 sau 0 după cum al j_-lea segment vertical de pe linia _i a fost trasat sau nu.

Date de ieșire

În fișierul de ieșire biscuit.out se va scrie numărul de pătrate pe care le poate închide jucătorul la mutare.

Restricții

• 2 ≤ M, N ≤ 1.000

Exemplu

biscuit.in	biscuit.out	Explicație
5 6 10101 01000 10111 10011 01011 111111 100101 111000 010101	14

Explicație

În figura de mai sus, segmentele negre sunt cele date la intrare. Jucătorul la mutare poate trasa segmentele verzi pentru a închide, în ordine, pătratele 1-14 (ordinea nu este unică). Segmentele gri sunt cele rămase netrasate după mutare.