Fișierul intrare/ieșire	vitraliu.in, vitraliu.out	Sursă	ad-hoc
Autor	Cristian Frâncu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	1

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

Vezi soluțiile trimise | Statistici

Vitraliu (clasa a 6-a)

Trolilor le plac culorile. Ei creează vitralii, adică sticle cu pătrățele de diverse culori. Toate vitraliile sunt sticle de formă pătrată cu pătrățele colorate aranjate în N linii și N coloane. Branch, mai morocănos din fire, a creat două vitralii N ori N, doar cu pătrățele albe (transparente) și gri. Ele au o proprietate interesantă: când le suprapui, două pătrățele gri suprapuse se vor vedea ca un pătrățel negru!

Cerință

Poppy vrea să știe cum să suprapună cele două vitralii astfel încât să obțină cât mai multe pătrățele negre.

Date de intrare

Fișierul de intrare vitraliu.in conține două vitralii astfel:

• Pe prima linie vor fi N pătrățele codificate cu 0 pentru un pătrățel alb, sau 1 pentru un pătrățel negru.
• Pe a doua linie vor fi următoarele N pătrățele, cea de-a doua linie a primului vitraliu.
• ...
• Pe a n-a linie vor fi N pătrățele, ultima linie din primul vitraliu.

În continuare fișierul conține încă N linii corespunzătoare celui de-al doilea vitraliu, astfel:

• Pe linia n+1 vor fi N pătrățele, prima linie a celui de-al doilea vitraliu.
• Pe linia n+2 vor fi N pătrățele, cea de-a doua linie a celui de-al doilea vitraliu.
• ...
• Pe linia 2n vor fi N pătrățele, ultima linie din al doilea vitraliu.

Date de ieșire

În fișierul de ieșire vitraliu.out veți scrie un singur număr, numărul de pătrățele negre maxim pe care îl poate obține Poppy suprapunând cele două vitralii.

Restricții

• Vitraliile sunt de maxim 500 ori 500 pătrățele.
• Suprapunerile sunt complete, nu se acceptă să rămână colțuri în afară.
• Dimensiunea minima a unui vitraliu este de 3 × 3.

Exemple

Explicație la primul exemplu

Fișierul de intrare codifică următoarele două vitralii:

Formăm toate suprapunerile posibile, rotind și întorcând pe cealaltă față al doilea vitraliu:

Numărul maxim de pătrățele negre este 4. Acest număr se obține în două dintre suprapunerile posibile.