echilibrare

Se consideră o matrice $A$ = $(a_{i, j})$, $1 \leq i, j \leq n$ (matrice pătratică de ordin $n$ cu liniile şi coloanele indexate de la $1$ la $n$).
Se cere să se construiască o matrice $B = (b_{i, j})$, $1 \leq i, j \leq n$ cu următoarele proprietăţi.

• $(a_{i,j}) \leq (b_{i,j})$, $\forall 1 \leq i, j \leq n$
• $(b_{i,j}) + (b_{i+1, j+1}) = (b_{i+1,j}) + (b_{i,j+1})$, $\forall\ 1 \leq i, j \leq 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$).

Cerinţă

Cunoscând o matrice oarecare cu elemente numere naturale să se determine o altă matrice echilibrată cu elementele numere naturale îndeplinind condiţiile din enunţ.

Date de intrare

Fisierul de intrare echilibrare.in va contine pe prima linie numarul $n$ cu semnificatie din enunt. Vor urma $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.

Date de ieșire

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

Restricții și precizări

• $1 \leq n \leq 50$
• Elementele din matricea iniţială sunt numere naturale cu valori mai mici sau egale decât $35 \ 000$.
• Elementele din matricea finală sunt numere naturale şi valoarea lor poate depăşi $35 \ 000$.
• 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.

Exemplu

echilibrare.in

4
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 1

echilibrare.out

16
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Explicație

Matricea din fişierul de ieşire are suma elementelor $16$, are fiecare element mai mare sau egal decât elementul corespunzător al matricii din fişierul de intrare, este echilibrată şi are suma elementelor minimă posibil.