• jocul începe la nivelul n,când se împarte matricea inițială în 4 matrici disjuncte de dimensiunea 2n-1;
• fiecare dintre cei doi jucători alege o matrice dintre cele 4 și adună la punctajul său numărul de valori de 1 conținut de matricea aleasă. Dacă ambii jucători aleg aceeași matrice doar jucătorul A adună la punctajul său numărul de valori de 1 din matrice;
• pentru fiecare nivel, după împărțirea matricei inițiale, matricele rezultate vor fi numerotate asemănător figurii;

• la nivelul n-1 fiecare dintre matricele alese de jucători se împart în 4 matrici disjuncte de dimensiunea 2n-2. Fiecare dintre cei doi jucători aleg o matrice din cele noi formate.
• pentru fiecare nivel jucat fiecare jucător trebuie să aleagă o matrice;
• jocul continua cu nivelele n-2, n-3, etc;
• jocul se termină când dimensiunea matricelor alese este 1;

Scopul jocului este obținerea sumei maxim posibile prin adunarea punctajelor celor doi jucători. Dacă există mai multe posibilități de obținere a acestei sume, fiecare jucător va alege matricele cu număr de ordine mai mic.

Exemplu: pentru n=3, vom simula un joc:
Jucătorul A alege matricea ce are colțul stânga-sus în (1,1), numerotat cu 1, Punctaj Sum_A = 7.

Jucătorul B alege matricea ce are colțul stânga-sus în (5,1), numerotat cu 3. Punctaj Sum_B = 5.

Jucătorul A alege matricea ce are colțul stânga-sus în (1,1), numerotat cu 1. Punctaj Sum_A = 7 + 3 = 10.

Jucătorul B alege matricea ce are colțul stânga-sus în (7,1), numerotat cu 3. Punctaj Sum_B = 5 + 3 = 8.

Jucătorul A alege matricea ce are colțul stânga-sus în (1,2), numerotat cu 2. Punctaj Sum_A = 10 + 1 = 11.

Jucătorul B alege matricea ce are colțul stânga-sus în (7,2), numerotat cu 2. Punctaj Sum_B = 8 + 1 = 9.

Jucătorul A a obținut Sum_A = 11, secvența alegerilor efectuate fiind: 1, 1, 2.

Jucătorul B a obținut Sum_B = 9, secvența alegerilor efectuate fiind: 3, 3, 2.

Cerința

Pentru un n număr natural dat și o matrice binară de dimensiunea 2n, se cere să se determine punctajul maxim obținut de cei doi jucători. Se cere și determinarea unei strategii de alegere a matricelor la fiecare pas care să ducă la obținerea punctajului maxim.

Date de intrare

Fișierul de intrare margi.in conține pe prima linie un număr natural C. Pe linia a doua se află un număr natural n. Pe următoarele 2n linii, elementele matricei binare.

Date de ieșire

Fișierul de ieșire margi.out conține pe prima linie suma maximă care se poate obține prin însumarea punctajelor celor doi jucători. În cazul în care C = 1 în fișierul de ieșire va apărea doar această valoare. Dacă C = 2 fișierul de ieșire va conține, în continuare:
Pe cea de-a doua linie se vor scrie n numere ce reprezintă secvența de matrici alese de jucătorul A.
Pe cea de-a treia linie se vor scrie n numere ce reprezintă secvența de matrici alese de jucătorul B.
Secvențele de matrice alese de cei doi trebuie să respecte următoarele două condiții:
1) suma celor două punctaje obținute de cei doi jucători este maximă. Pot exista mai multe secvențe de matrici care au suma maximă.
2) Fie An, An-1, …, A1 secvențele de matrici alese de A, respectiv Bn, Bn-1, …, B1, secvențele de matrici alese de B, la nivelele n, n-1, …, 2, 1. Dacă compunem șirul An, Bn, An-1, Bn-1, An-2, Bn-2, …, A1, B1, dintre toate șirurile posibile care dau suma maximă, trebuie ales cel șirul minim lexicografic.

Restricții și precizări

• C poate fi 1 sau 2
• 2 ≤ n ≤ 10
• Spunem că șirul X este mai mic lexicografic decât șirul Y, dacă există o poziție i, astfel încât X1=Y1, X2=Y2, …., Xi-1=Yi-1, iar Xi<Yi
• Pentru teste în valoare de 30 de puncte avem C = 1.

Exemplul 1:

margi.in

1
2
0000
0100
0000
0000

margi.out

2

Explicație

Suma maximă este (0 + 1) + (0 + 1) = 2. Dacă am fi avut C = 2, pe liniile 2 și 3 ar mai fi apărut:
1 1
1 4

Exemplul 2:

margi.in

2
3
01001100
11100011
00101000
11000000
00000000
01100100
01000000
11000010

margi.out

20
1 1 2
3 3 2 

Explicație

Suma maximă este (7 + 5) + (3 + 3) + (1 + 1) = 20. Exemplul din figura de mai sus.