Se consideră o tablă de şah de dimensiune n. Se ştie că în fiecare pătrăţel se găseşte câte o piesă de şah. Fiecare piesă de şah are o anumită importanţă, dată de o valoare scrisă pe ea. Valoarea piesei este un număr natural. Se doreşte separarea pieselor de şah printr-o linie frântă formată numai din segmente (laturi) ale pătrăţelelor tablei, în două regiuni (regiunea din stânga şi regiunea din dreapta) astfel încât:
• să nu existe două segmente orizontale pe aceeaşi dreaptă orizontală;
• să nu existe două segmente verticale pe aceeaşi linie de pătrăţele ale tablei;
• pe fiecare linie cu pătrăţele a tablei de şah există măcar un element atât în regiunea din stânga, cât şi în regiunea din dreapta;
• linia frântă începe pe prima linie de pătrăţele şi se termină pe ultima linie de pătrăţele;
• valoarea absolută a diferenţei dintre suma elementelor regiunii din stânga şi suma elementelor regiunii din dreapta este minimă.
Cerinţă
Se cere să se determine o linie frântă cu proprietăţile anterioare.
Date de intrare
Fişierul de intrare linie.in conţine pe prima linie numărul n. Pe fiecare dintre următoarele n linii se află câte n numere naturale separate prin câte un spaţiu, reprezentând elementele tabloului.
Date de ieşire
În fişierul de ieşire linie.out se va scrie pe prima linie suma elementelor regiunii din stânga. Pe cea de a doua linie se va scrie suma elementelor regiunii din dreapta. Pe cea de a treia linie se vor scrie n numere naturale separate prin câte un spaţiu. Al i-lea număr de pe linia 3 a fişierului de ieşire reprezintă indicele maxim de coloană al elementelor care se află pe tablă în regiunea din stânga pe linia i. În cazul în care există mai multe soluţii în fişier se va scrie una singură.
Restricţii
2 <= n < 13
Toate elementele tabloului sunt numere naturale <= 32000.
