K0 - Káble

Peťo sa rozhodol kúpiť si byt. Nemal dosť peňazí na kúpu bytu v novostavbe, preto kúpil panelákový byt v pôvodnom stave. Zatiaľ má kde bývať (u rodičov), tak sa rozhodol, že si ho prerobí svojpomocne, aj keď to bude dlhšie trvať. Pri dôkladnej obhliadke zistil, že niektoré zásuvky nefungujú a elektrické vedenie je dvojžilové (dnešným normám už nevyhovujúce) a hliníkové (teraz sa používa medené). Rozhodol sa teda pre výmenu kabeláže. Pripravil si projekt, kde chce mať zásuvky a odmeral si jednotlivé vzdialenosti (medzi zásuvkami, ako aj k rozvodnej skrinke). V elektrickej sieti sa môžu káble rozvetvovať, ale po rozvetvení sa už nemôžu ďalej spojiť (uzavrel by sa okruh a nastal skrat). Odmeral si iba tie úseky, do ktorých bude dávať kábel. Potreboval by zistiť, koľko káblu mu treba objednať. Jeho strýko Juraj mu poradil, nech si každú izbu napojí na zvlášť istič (všetky ističe musia byť v rozvodnej skrini). To ale znamená, že na niektorom úseku (zásuvka-zásuvka / zásuvka-rozvodná skriňa) bude viac káblov vedľa seba. Takže Peťo potrebuje vedieť aj najviac koľko káblov mu bude uložených vedľa seba, aby vedel kúpiť dostatočne široké lišty (do celého bytu kúpi jednotnú šírku).

Úloha

Vstup

• rozvodná skrina je označená číslom 1
• v prvej izbe je jedna zásuvka - číslo 2
• v druhej izbe sú dve zásuvky - číslo 3, 4
• v tretej izbe sú tri zásuvky - čísla 5, 6, 7

Výstup

Príklad 1

Vstup:

2 2
1 2 100
2 3 50
3 4 40
3 5 40

Výstup:

2 380

Príklad 2

Vstup:

1 1 1 2
1 2 1000
2 3 100
2 4 100
3 5 100
4 6 100

Výstup:

4 4600