Fişierul intrare/ieşire:	flooow.in, flooow.out	Sursă	Lot Râmnicu Vâlcea 2015 - Baraj 3 Seniori
Autor	Mihai Nitu, Murtaza Alexandru	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.1 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

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

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

• 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

Exemplu

Cum se trimit solutii?