Fie o matrice lidoriană de x linii şi y coloane. Liniile matricei se numerotează de jos în sus, cu numere de la 0 la x-1. Coloanele matricei se numerotează de la dreapta la stânga, cu numere de la 0 la y-1. Matricea lidoriană este formată doar din valori „1” şi „0”.



Pentru fiecare linie i, se calculează sli ca suma tuturor produselor dintre a(i,j) şi 2j. Pentru fiecare coloană k, se calculează sck ca suma tuturor produselor dintre a(i,k) şi 2i .



Fie S1 suma tuturor sumelor calculate pe linii şi fie S2 suma tuturor sumelor calculate pe coloane.
S1= Sl0+ Sl1+ Sl2 S2= Sc0+ Sc1+ Sc2 + Sc3
Considerăm t=S1+ S2. Se înţelege prin „mutare” o interschimbare între oricare două valori „1” şi „0” din matrice.
Jocul lidorian presupune executarea unui număr minim de mutări, astfel încât valoarea lui t să fie minimă.

Cerinţă

Să se scrie un program care să permită calcularea valorii minime a lui t. Pentru această valoare a lui t, se cere să se determine numărul minim de mutări necesare.

Date de intrare

Fişierul de intrare joc8.in conţine în ordine, pe linii:
x y număr de linii,număr de coloane despărţite printr-un spaţiu
ax-1,y-1 ax-1,y-2 … ax-1,0 elementele liniei x-1, fără spaţii între ele
ax-2,y-1 ax-2,y-2 … ax-2,0 elementele liniei x-2, fără spaţii între ele
…
a0,y-1 a0,y-2 … a0,0 elementele liniei 0, fără spaţii între ele

Date de ieşire

Fişierul de ieşire joc8.out conţine, în ordine, pe prima linie, valoarea t, apoi numărul minim de mutări, cu un singur spaţiu între ele.

Restricţii

2 <= x, y <= 12
matricea conţine cel puţin o cifră de 1

Exemple

joc8.in	joc8.out	Explicaţii
5 6 100010 010000 000001 000010 011000	28 5

autor: Prof. Rodica Pintea

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com