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).

prof. Marius Nicoli

Colegiul Naţional „Fraţii Buzeşti” Craiova

mariusnicoli@yahoo.com