U Lukinom gradu nalazi se N restorana označenih brojevima od 1 do N, za svakog se pronađe ponešto. Tako i vlasnici restorana također imaju svoje omiljene restorane koje rado posjećuju. Ako vlasnika restorana pitamo za preporuku, on će, osim svojeg restorana, preporučiti i svoje omiljene restorane, ali i sve restorane koje bi preporučili njihovi vlasnici.</p>

Donja tablica prikazuje jedan primjer sa četiri restorana: 

Luka planira obići nekoliko restorana i to na sljedeći način:

• Prvi restoran odabrat će proizvoljno.
• Svaki slijedeći restoran odabrat će tako da će pitati vlasnika trenutnog restorana za preporuku, te od preporučenih restorana odabrati jedan u kojem još nije bio.
• Luka može u bilo kojem trenutku završiti s obilaskom restorana.

Svaki restoran A ima dvije cijene X_A i Y_A za glavni meni. Prilikom ulaska u restoran, vlasnik će Luku upitati tko mu je preporučio njegov restoran. Ukoliko je ta osoba vlasnik restorana B, tada će Luka platiti:

• X_A kuna, ako vlasnik restorana A preporučuje restoran B,
• Y_A kuna, inače. Ovaj iznos Luka plaća i u prvom restoranu.

Neka je K najveći broj restorana koje Luka može posjetiti na ovaj način. Za svaki broj k između 1 i K potrebno je izračunati koliko najmanje kuna treba Luki ako želi posjetiti točno k restorana. 

입력 형식

U prvom redu nalazi se cijeli broj N (1 ≤ N ≤ 1000), broj restorana.</p>

U svakom od sljedećih N redova nalazi se nekoliko cijelih brojeva.

Prva dva broja u i-tom redu su cijene glavnog menija X_i , Y_i (1 ≤ X_i , Y_i ≤ 10000), dok je treći broj O_i (0 ≤ O_i < N) broj restorana omiljenih vlasniku restorana i. Preostalih O_i brojeva predstavlja oznake njegovih omiljenih restorana; te oznake su međusobno različite i nijedna nije jednaka i.

출력 형식

Ako je K najveći broj restorana koje Luka može posjetiti, tada je potrebno ispisati K redova. U k-ti red potrebno je ispisati najmanji broj kuna koje Luka mora platiti da bi posjetio točno k restorana. 

예제 입력 1

4
100 200 1 2
200 300 1 3
200 250 2 2 4
200 300 0

예제 출력 1

200
450
650
950

예제 입력 2

9
100 100 0
300 400 1 4
350 500 1 2
550 600 3 7 3 2
900 300 2 7 6
250 400 1 5
900 900 2 9 8
400 500 1 9
500 400 0

예제 출력 2

100
550
950
1450
2150
3050

힌트

Najjeftiniji način za posjetiti jedan restoran je posjetiti restoran 1 (200 kn).
Najjeftiniji način za posjetiti dva restorana je posjetiti restoran 3 (250 kn), pa zatim restoran 2 (200 kn).
Najjeftiniji način za posjetiti tri restorana je posjetiti restoran 1 (200 kn), restoran 3 (250 kn), te konačno restoran 2 (200 kn).
Najjeftiniji način za posjetiti četiri restorana je posjetiti restoran 1 (200 kn), restoran 3 (250 kn), restoran 2 (200 kn), te konačno restoran 4 (300 kn).