Primarul oraşului Xcity a hotărât să cumpere pentru
piaţa principală o instalaţie electrică în vederea sărbătorilor de iarnă.
Aceasta are formă dreptunghiulară cu n linii şi m coloane. În dreptul
fiecărei coloane se află un comutator în urma acţionării căruia becurile
de pe acea coloană îşi schimbă configuraţia (cele aprinse se sting,
cele stinse se aprind). La punerea sub tensiune a instalaţiei aceasta
are o configuraţie predefinită a becurilor (unele sunt stinse, altele
aprinse). Primarul doreşte ca pentru seara de Crăciun, în configuraţia
instalaţiei să fie cât mai multe stele. O stea este o configuraţie de
becuri aprinse care are exact forma din figură:
*
*
*
*
*
Cerinţă
Dându-se configuraţia instalaţiei la punerea sub tensiune, să se determine
numărul maxim de stele care se pot obţine.
Date de intrare
Fisierul stele.in conţine pe prima linie două numere naturale n m separate printr-un spaţiu (numărul
de linii respectiv de coloane).
Pe următoarele n linii se afla câte m valori 0 sau 1, separate prin cate un spaţiu
reprezentând configuraţia instalaţiei la punerea sub tensiune (1-bec
aprins, 0-bec stins).
Date de ieşire
Fisierul stele.out conţine o singura linie pe care va fi scris numărul maxim de stele ce se
pot obţine.
Restricţii
1 <= n <= 100
1 <= m <= 10
Două stele se pot suprapune parţial sau pot fi formate din becuri vecine.
Exemplu
stele.in
stele.out
Explicatie
3
4
1 0 0 0
1 0 0 0
0 0 0 1
2
Dacă se intorc coloanele 2,3,4 se obţine 1 1 1 1
1 1 1 1
0 1 1 0
Cele două stele au centrul in poziţiile (2,2) şi (2,3).