Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: rivers.in

Rezultatų failas: rivers.out

Jei norite pateikti savo sprendimą - prisijunkite.

Upės

Baitlando šalyje gausu miškų ir upių. Mažos upės įteka į dideles, tos į didesnes, kol galiausiai visos suteka į vieną didžiausią upę. Pastaroji įteka į jūrą netoli Baito miesto.

Šalyje yra n medkirčių gyvenviečių, kiekviena kurių įsikūrusi prie kurios nors iš upių. Baito mieste yra didžiulė lentpjūvė, kuri apdoroja visus šalyje nukirstus medžius. Medžiai plukdomi iš gyvenviečių upėmis į šią lentpjūvę Baito mieste. Siekdamas sumažinti medžių transportavimo kainą, Baitlando šalies valdovas nusprendė pastatyti gyvenvietėse k papildomų lentpjūvių. Pastačius papildomas lentpjūves nebereiks plukdyti visų medžių į Baito miestą, o bus galima juos apdoroti artimiausioje pasroviui lentpjūvėje. Suprantama, jei gyvenvietėje yra lentpjūvė, tai aplink ją nukirstų medžių plukdyti upe nereikia. Atkreipiame dėmesį, kad upės neišsišakoja. Todėl iš kiekvienos gyvenvietės yra vienintelis kelias pasroviui upėmis į jūrą Baito mieste.

Valdovo apskaitininkai suskaičiavo, kiek medžių nukertama aplink kiekvieną gyvenvietę per metus. Jums reikia nuspręsti, kur pastatyti lentpjūves, kad medžių plukdymo upėmis bendros išlaidos per metus būtų kuo mažesnės. Vieno medžio plukdymas upe vieną kilometrą kainuoja vieną centą.

Parašykite programą, kuri suskaičiuotų minimalią medžių plukdymo upėmis kainą, pastačius papildomas lentpjūves.

Pradiniai duomenys

Pirmoje eilutėje pateikiami du sveikieji skaičiai: n — gyvenviečių skaičius, neįskaitant Baito miesto (2\\len\\le100) ir k — lentpjūvių skaičius, kurias reikia papildomai pastatyti (1\\lek\\le50 ir k\\len). Gyvenvietės sunumeruotos 1,2,\\dots,n, o Baito miestui priskirtas numeris 0.

Kiekvienoje iš tolesnių n eilučių įrašyta po tris sveikuosius skaičius. i+1 eilutėje įrašyta:

  • w_i — skaičius medžių, nukirstų per metus aplink i-tąją gyvenvietę (0\\lew_i\\le10000),
  • v_i — artimiausia gyvenvietė (arba Baito miestas), esanti pasroviui nuo i-tosios gyvenvietės (0\\lev_i\\len),
  • d_i — atstumas upe (kilometrais) nuo i-tosios gyvenvietės iki v_i (1\\led_i\\le10000).

Žinoma, kad medžių plukdymo į Baito miesto lentpjūvę bendra kaina neviršija 2 000 000 000 centų per metus.

Rezultatai

Vienintelėje eilutėje reikia įrašyti vieną sveikąjį skaičių: mažiausią medžių plukdymo upe kainą (centais).

Pavyzdys

Duomenys Rezultatai 
4 2
1 0 1
1 1 10
10 2 5
1 2 3
 
4