Cerință

Dintr-o matrice $mat$ de $N \times N$ se construiesc $3$ matrice $v_1$, $v_2$, $v_3$ cu proprietățile următoare:
Pentru fiecare celulă din matrice $(i, j)$, $1 \leq i, j \leq N$:

• $0 \leq v_{1 (i, j)}<i$;
• $0 \leq v_{2 (i, j)}<j$;
• $v_{3 (i, j)}=$ suma submatricei cu colțul stânga sus $(i-v_{1 (i, j)}, j-v_{2 (i, j)})$ și cu colțul dreapta jos $(i, j)$ din matricea $mat$

Vi se dau $N$, $K$ și matricele $v_1$, $v_2$, $v_3$. Să se afișeze un mod de a schimba exact $K$ valori din matricea $mat$, astfel încât suma valorilor din $v_3$ devine minimă. De asemenea, la final, va trebui să afișați suma minimă. Se poate alege ca elementul din celula $(i, j)$ din matricea $mat$ să ramână la fel, caz în care veți afișa ($i$, $j$, elementul matricei $mat$ din celula $(i, j)$).

Date de intrare

Pe prima linie a fișierului de intrare partsum.in se găsesc două numere întregi, $N$ si $K$. Pe următoarele $N$ linii se vor afla câte $N$ valori, reprezentând valorile din $v_1$. Pe următoarele $N$ linii se vor afla câte $N$ valori, reprezentând valorile din $v_2$. Pe următoarele $N$ linii se vor afla câte $N$ valori, reprezentând valorile din $v_3$.

$\bold{Atenție!}$ În teste, nu există linii goale între matricele $v_1$, $v_2$ și $v_2$, $v_3$. Acestea au fost puse doar pentru clarificarea exemplului!

Date de ieșire

Pe primele $K$ linii ale fișierului de ieșire partsum.out se vor afla trei valori $lin_i, col_i, x_i$, reprezentând faptul că valoarea din celula $(lin_i, col_i)$ se va schimba în $x_i$. Pe linia a $K+1$-a se va afla suma minimă formată.

$\bold{Atenție!}$ Dacă cel puțin o valoare dintre $lin_i$ sau $col_i$ nu se află în intervalul $[1, N]$, verdictul va fi Răspuns Greșit. De asemenea, dacă cel puțin o valoare $x_i$ nu se află in întervalul $[0, 3 \times 10^6]$, verdictul va fi Răspuns Greșit.

Restricții și precizări

• $1 \leq N \leq 600$;
• $1 \leq K \leq N^2$;
• Pot exista mai multe soluții corecte, se va accepta oricare dintre ele
• Daca cele $K$ schimbări nu duc la suma valorilor din $v_3$ fiind suma afișată pe linia a $K+1$-a, se vor acorda $0$ puncte!
• Se garantează că matricele $v_1$, $v_2$ şi $v_3$ provin dintr-o matrice $mat$
• $0 \leq v_{3 (i, j)} \leq 10^{12}$
• Se garantează că elementele matricei $mat$ sunt numere naturale

Exemplul 1

partsum.in

2 1
0 0
0 0

0 1
0 0

2 5
3 3

partsum.out

1 1 0
9

Explicație

Matricea $mat$ din care provin $v_1$, $v_2$ si $v_3$ este:

2 3
3 3

Daca schimbăm valoarea $2$ în $0$, din celula $(1, 1)$, sumele de pe rândul $1$ vor deveni $0 \ 3$, iar suma valorilor din $v_3$ devine $0+3+3+3=9$. Aceasta este suma minimă care se poate forma dacă schimbăm cel mult un element.