AxonT vrea să vadă dacă aveţi flooow. Se da o reţea de flux, cu costuri pe muchii, alcătuită din următoarele componente:

* Nodurile $S$ si $T$, dispuse fiecare pe câte un rand.
* Mulţimea $V$ de noduri dispusă pe $N$ rânduri, fiecare rând fiind alcătuit din $L[i]+1$ noduri $(1≤ i ≤ N)$.
* Nodul $D$ asezat pe ultimul rând.
* De la nodul $S$ la nodul $T$ este o muchie de capacitate $K$ şi cost $0$.
* De la nodul $T$ la fiecare nod de pe primul rând din multimea $V$ sunt muchii de capacitate $K$ şi cost $0$.
* De la fiecare nod de pe rândul $i$ la fiecare nod de pe rândul $i+1$ (din multimea $V$) există muchie (orientată) de capacitate $K$ şi cost $0$.
* De la fiecare nod de pe ultimul rând (rândul $N$) la nodul $D$ sunt muchii de capacitate $K$ şi cost $0$.
* De la al $j$-lea nod de pe linia $i$ către al $j+1$-lea nod de pe linia $i$, $1 ≤ i ≤ N$ si $1 ≤ j ≤ L[i]$) există o muchie de capacitate $1$ şi cost $A[i][j]$.

* Nodurile S si T, dispuse fiecare pe câte un rand.
* Mulţimea V de noduri dispusă pe N rânduri, fiecare rând fiind alcătuit din L[i]+1 noduri (1≤ i ≤ N).
* Nodul D asezat pe ultimul rând.
* De la nodul S la nodul T este o muchie de capacitate K şi cost 0.
* De la nodul T la fiecare nod de pe primul rând din multimea V sunt muchii de capacitate K şi cost 0.
* De la fiecare nod de pe rândul i la fiecare nod de pe rândul i+1 (din multimea V) există muchie (orientată) de capacitate K şi cost 0.
* De la fiecare nod de pe ultimul rând (rândul N) la nodul D sunt muchii de capacitate K şi cost 0.
* De la al j-lea nod de pe linia i către al j+1-lea nod de pe linia i, 1 ≤ i ≤ N si 1 ≤ j ≤ L[i]) există o muchie de capacitate 1 şi cost A[i][j].

h2. Cerinta

Ştiind că $S$ este sursa fluxui si $D$ este destinaţia, şi dându-se numerele $N, K$, precum şi matricea $A$, să se determine fluxul maxim de cost maxim pe reteaua descrisă.
 
!problema/flooow?floow_image.png!

Ştiind că S este sursa fluxui si D este destinaţia, şi dându-se numerele N, K, precum şi matricea A, să se determine fluxul maxim de cost maxim pe reteaua descrisă.

h2. Date de intrare

Pe prima linie a fişierului *flooow.in* se găsesc $2$ numere $N$ şi $K$ cu semnificaţia din enunţ/desen. Vor urma $N$ linii ce descriu matricea $A$. Fiecare dintre cele $N$ linii începe cu un număr $L$, numărul de muchii dintre nodurile de pe această linie (vor fi $L+1$ noduri). Tot pe aceasta linie vor urma $L$ numere naturale, costurile celor $L$ muchii.
 

h2. Date de ieşire

Pe prima linie a fişierului *flooow.out* se vor afişa două numere naturale separate prin câte un spaţiu: cantitatea maximă de flux care poate fi transportata de la $S$ la $D$ şi costul maxim pentru a transporta această cantitate de flux.

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

h2. Restricţii

* $1 <= N <= 200 000$
* $1 <= numărul de noduri de pe un rând <= 200 001$
* $1 <= numarul de elemente din matricea A <= 200 000$
* $-10 000 <= orice valoare din matricea A <= 10 000$
* $1 <= K <= 5 000$

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

h2. Exemplu
table(example). |_. flooow.in |_. flooow.out |

| 3 2
5 1 2 -1 2 1
5 3 -2 3 -2 3
2 -1 -2
| 2 13

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="flooow") ==