Plante

Oficial, m-am răzbunat.

Toată lumea știe că plantele sunt ca niște arbori (grafuri neorientate conexe aciclice). O plantă are un număr $M$ de fructe (numerotate de la $1$ la $M$) specific acesteia, iar fructele sunt conectate de $M - 1$ ramuri, astfel încât să poți ajunge de la fiecare fruct la oricare alt fruct prin intermediul lor. Toată lumea mai știe și că fiecare fruct dintr-o plantă este caracterizat de frumusețea sa, $F$. De asemenea, toți grădinarii știu că se poate calcula efortul culegerii fructelor unei plante (notată cu $E$) în felul următor:

• Alegem un fruct $S$ dintre cele $M$ ale plantei, acesta devenind fructul principal al plantei.
• Însumăm, pentru fiecare fruct $U$ din plantă, frumusețea fructului $U$ înmulțit cu distanța dintre fructele $S$ și $U$ în plantă (distanța dintre două fructe într-o plantă este numărul minim de ramuri care trebuie traversate pentru a ajunge de la un fruct la celălalt).
• Efortul plantei va fi egal cu maximul dintre sumele obținute pentru toate fructele principale $S$ alese.
  Formal, efortul unei plante se calculează astfel:

Zanagludeuba, grădinarul viclean din Lamangaï, a găsit în laboratorul dușmanului său, Emargni cel Iubitor, o mulțime de $N$ plante foarte valoroase, numerotate de la stânga la dreapta cu numere de la $1$ la $N$. Acesta a observat că fiecare plantă este conectată cu vecinii săi. Pe scurt, planta $i$ este conectată cu plantele $i - 1$ și $i + 1$, cu excepția plantelor $1$ și $N$, care sunt conectate doar cu planta $2$, respectiv cu planta $N - 1$.
Zanagludeuba vrea să îi strice zen-ul adversarului său cât timp este în vacanță, așa că își propune să le distrugă, dar realizează rapid că plantele sunt prea puternic conectate. Astfel, el își dorește să despartă plantele una de cealaltă, adică să taie conexiunile plantelor între ele. El va trebui să facă exact $N - 1$ tăieturi (fiecare tăietură strică exact o conexiune), astfel încât, la final, toate plantele să nu aibă nicio conexiune.

Din păcate, Zanagludeuba întâmpină o problemă majoră: tăieturile îi ocupă timp, iar el este foarte leneș (iubește să îl enerveze pe Emargni, dar iubește mai mult să lucreze la informatică). Timpul total necesar pentru a despărți plantele este egal cu suma duratelor fiecăreia dintre cele $N - 1$ tăieturi. Timpul necesar unei tăieturi, notat cu $T$, între plantele $i$ și $i + 1$, se calculează în felul următor:

• Se notează cu $L$ mulțimea maximală a plantelor conectate între ele în stânga plantei $i$ și în care este inclusă aceasta, adică mulțimea tuturor plantelor la care poți ajunge plecând de la planta $i$ către stânga și parcurgând doar conexiuni netăiate.
• Se notează cu $R$ mulțimea maximală a plantelor conectate între ele în dreapta plantei $i + 1$ și în care este inclusă aceasta, adică mulțimea tuturor plantelor la care poți ajunge plecând de la planta $i + 1$ către dreapta și parcurgând doar conexiuni netăiate.
• Se notează cu $Rec(Q)$ recolta mulțimii de plante $Q$, adică suma numărului de fructe $M$ ale plantelor din mulțimea $Q$.
• Se notează cu $Cab(Q)$ calibrul mulțimii de plante $Q$, adică maximul dintre eforturile $E$ ale plantelor din mulțimea $Q$.
• $T = \left\lfloor \sqrt{Rec(L)} \right\rfloor \cdot Cab(R) + \left\lfloor \sqrt{Rec(R)} \right\rfloor \cdot Cab(L)$.

În poza alăturată, putem observa $N = 6$ plante. Fiecare plantă are caracteristicile sale trecute sub ea. De exemplu, planta $3$ are $M_3 = 2$ și $E_3 = 19$. Unele conexiuni sunt deja tăiate, iar conexiunile rămase sunt între plantele $2 - 3$, $3 - 4$ și $5 - 6$. Dacă vrem să calculăm timpul necesar pentru a tăia conexiunea dintre plantele $3$ și $4$, vom proceda în felul următor:

• Mulțimea $L$ este alcătuită din plantele $2$ și $3$.
• Mulțimea $R$ este alcătuită doar din planta $4$.
• $Rec(L) = M_2 + M_3 = 5 + 2 = 7$, iar $Rec(R) = M_4 = 6$.
• $Cab(L) = max(E_2, E_3) = max(6, 19) = 19$, iar $Cab(R) = max(E_4) = max(14) = 14$.
• $T = \left\lfloor \sqrt{7} \right\rfloor \cdot 14 + \left\lfloor \sqrt{6} \right\rfloor \cdot 19 = 2 \cdot 14 + 2 \cdot 19 = 66$

Cerință

Emargni cel Iubitor a aflat de planul lui Zanagludeuba de la prietenul său, Stacedfas, chiar când Zanagludeuba își începea treaba, dar se delectează prea bine în vacanță și vrea să se întoarcă acasă cât mai târziu. Acesta v-a angajat pe voi să găsiți cea mai lungă durată $D$ pe care Emargni o mai poate petrece în vacanță, pentru a-l putea prinde sigur pe grădinarul viclean în fapt, oricum ar executa acesta tăieturile (Emargni se poate teleporta acasă instant sau chiar în trecut).

Date de intrare

Pe prima linie a fișierului de intrare plante.in se găsește un număr natural $N$, reprezentând numărul de plante.
Pe următoarele linii sunt descrise fiecare dintre cele $N$ plante în ordine crescătoare a numărului lor de ordine, astfel:

• Pe prima linie a descrierii se găsește un număr natural $M_i$, reprezentând numărul de fructe ale plantei $i$.
• Pe următoarea linie a descrierii se găsesc $M_i$ numere naturale: $F_1, F_2, ..., F_{M_i}$, separate printr-un spațiu, reprezentând frumusețea fructelor din planta $i$.
• Pe următoarele $M_i - 1$ linii ale descrierii se găsesc câte două numere naturale $x$ și $y$, separate printr-un spațiu, cu semnificația că există o ramură între fructele $x$ și $y$ în planta $i$.

Date de ieșire

Pe prima linie a fișierului de ieșire plante.out se va găsi un singur număr întreg $D$, reprezentând durata maximă pe care o mai poate petrece Emargni în vacanță, pentru a-l putea prinde sigur pe Zanagludeuba în fapt.

Restricții și precizări

• $2 \leq N \leq 500$;
• $4 \leq \sum_{\substack{i=1}}^{N} M_i \leq 1 \ 000 \ 000$;
• $-10 \ 000 \leq F_i \leq 10 \ 000$;
• Efortul $E$ al unei plante poate fi negativ, grădinarilor făcându-le plăcere să culeagă fructele acestei plante;
• Notăm cu $dist(x, y)$ distanța dintre fructele $x$ și $y$ într-o plantă și este egală cu numărul minim de ramuri care trebuie traversate pentru a ajunge de la $x$ la $y$;
• Distanța de la un fruct la el însuși este egală cu $0$;
• $\lfloor X \rfloor$ reprezintă cel mai mare număr întreg mai mic sau egal decât $X$. De exemplu, $\lfloor 8.3 \rfloor = 8$, iar $\lfloor 8 \rfloor = 8$;
• Durata maximă $D$ pe care o mai poate petrece Emargni în vacanță poate fi negativă, caz în care Emargni se va teleporta în trecut pentru a-l prinde pe Zanagludeuba, fiindcă Emargni face parte din specia Rendangster, care este cunoscută pentru puterile sale supranaturale;

  #	Punctaj	Restricții
  0	0	Exemplul
  1	9	$N = 2$ și $4 \leq \sum_{\substack{i=1}}^{N} M_i \leq 5 \ 000$
  2	17	$N = 2$
  3	11	$2 \leq N \leq 10$ și $M_i = 2$
  4	14	$2 \leq N \leq 10$ și $4 \leq \sum_{\substack{i=1}}^{N} M_i \leq 5 \ 000$
  5	13	$2 \leq N \leq 10$
  6	13	$M_i = 2$
  7	12	$4 \leq \sum_{\substack{i=1}}^{N} M_i \leq 5 \ 000$
  8	11	Fără restricții suplimentare

Exemplu

plante.in

3
2
3 4
2 1
3
2 3 5
1 2
3 1
6
2 1 3 1 2 4
2 1
6 5
3 4
3 5
1 3

plante.out

102

Explicație

Dimensiunile celor $N = 3$ plante sunt:

• $E_1 = 4$, fructul principal ales optim este $1$.
• $E_2 = 12$, fructul principal ales optim este $2$.
• $E_3 = 33$, fructul principal ales optim este $2$.

Zanagludeuba are două modalități de a tăia conexiunile plantelor:

• Taie mai întâi conexiunea dintre plantele $1$ și $2$, cu $T = 45$, apoi conexiunea $2 - 3$, cu $T = 57$. Timpul total este $102$.
• Taie mai întâi conexiunea dintre plantele $2$ și $3$, cu $T = 90$, apoi conexiunea $1 - 2$, cu $T = 16$. Timpul total este $116$.

Emargni trebuie să se întoarcă după $D = 102$ ca să îl poată prinde sigur pe Zanagludeuba.