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