Планування пікніка#6073
Брати Конторсія - відома циркова трупа клоунів, які славляться своєю здатністю втискуватися в найменші автомобілі у великій кількості. У міжсезоння вони збираються на щорічне зібрання Конкортиціоністів у місцевому парку. Оскільки брати стикаються не лише з проблемою тісноти, а й з фінансовими труднощами, вони прагнуть організувати вечірку так, щоб мінімізувати загальну кількість миль, які проїдуть їхні автомобілі (економлячи таким чином на бензині, зносі та амортизації). Для цього вони готові втиснутися в кілька автомобілів, необхідних для зменшення загальної кількості миль. Це часто означає, що один брат їде до іншого, залишає свій автомобіль і пересаджується в автомобіль брата. Однак у парку існує обмеження: на стоянці біля місця для пікніка може бути лише певна кількість автомобілів, що слід враховувати при плануванні. Крім того, через оплату за в'їзд у парк, якщо автомобіль брата прибув у парк, він повинен там залишитися; не можна висадити пасажирів і поїхати за іншими братами. Ваша циркова трупа має вирішити цю складну задачу, тому вам потрібно написати програму для мінімізації пройдених миль.
Перший рядок містить число - кількість доріг між братами або між братами і парком. Кожен з наступних рядків містить опис дороги у форматі name1 name2 dist, де name1 і name2 - імена двох братів або ім'я брата і слово Park (у будь-якому порядку), dist - відстань між ними. Дороги є двосторонніми, dist завжди позитивне. Максимальна кількість братів дорівнює , а довжина їхніх імен не перевищує символів. Після цих рядків слідує останній рядок, що містить ціле число - кількість автомобілів, які можуть поміститися на стоянці біля місця для пікніка. Вважайте, що завжди існує шлях від дому кожного брата до парку і що рішення завжди існує.
Виведіть рядок у форматі
Total miles driven: xxx
де xxx - загальна кількість миль, пройдених усіма автомобілями братів.
Приклад 1
Приклад 2