== include(page="template/taskheader" task_id="echilibrare") ==

Poveste şi cerinţă...

Se consideră o matrice $A = (a$~i,j~$), 1 ≤ i, j ≤ n  $ (matrice pătratică de ordin $n$ cu liniile şi coloanele indexate de la $1$ la $n$).
Se cere să se construiască o matrice matrice $B = (a$~i,j~$), 1 ≤ i, j ≤ n  $ cu următoarele proprietăţi.
 
# $(a$~i,j~$)$ ≤ $(b$~i,j~$)$ ∀ 1 ≤ i, j ≤ n
# $(b$~i,j~$)$ + $(b$~i+1,j+1~$)$ = $(b$~i+1,j~$)$ + $(b$~i,j+1~$)$ ∀ 1 ≤ i, j ≤ n - 1 ( o matrice cu această proprietate se numeşte matrice echilibrată )
# Suma elementelor din matricea $B$ este minimă. ( adică orice matrice care îndeplineşte primele două condiţii are suma elementelor mai mare sau egală decât suma elementelor matricei $B$).
 
h2. Cerinţă
 
Cunoscând o matrice oarecare cu elementle numere naturale să se determine o altă matrice echilibrată cu elementele numere naturale îndeplinind condiţiile din enunţ.

h2. Date de intrare

Fişierul de intrare $echilibrare.in$ ...

Fisierul de intrare #echilibrare.in# va contine $n$ linii fiecare conţinând câte $n$ numere naturale separate prin câte un spaţiu. Cele $n$ linii conţin elementele liniilor corespunzătoare din matricea iniţiala.

h2. Date de ieşire

În fişierul de ieşire $echilibrare.out$ ...

Fişierul de ieşire $echilibrare.out$ va conţine pe prima linie un singur număr reprezentând suma elementelor din matricea echilibrată cerută. Următoarele $n$ linii vor conţine câte $n$ numere naturale separate prin spaţiu reprezentănd elementele din matricea echilibrată găsită.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n≤ 50$
* Elementele din matricea iniţială sunt numere naturale cu valori mai mici sau egale decât $35000$.
* Elementele din matricea finală sunt numere naturale şi valoarea lor poate depăşi $35000$.
* Dacă există mai multe soluţii corecte se poate afişa oricare dintre acestea.
* Daca se determină doar suma corectă se vor obţine $60$ de puncte.

h2. Exemplu