Flooow

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$ și $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 \leq i \leq N)$.
• Nodul $D$ așezat 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 \leq i \leq N$ și $1 \leq j \leq L[i]$ există o muchie de capacitate $1$ și cost A[i][j].

Cerință

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

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.

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.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $1 \leq$ numărul de noduri de pe un rând $\leq 200 \ 001$;
• $1 \leq$ numarul de elemente din matricea $A \leq 200 \ 000$;
• $-10 \ 000 \leq$ orice valoare din matricea $A \leq 10 \ 000$;
• $1 \leq K \leq 5 \ 000$.

Exemplu

flooow.in

3 2
5 1 2 -1 2 1
5 3 -2 3 -2 3
2 -1 -2

flooow.out

2 13