Братья Конторсия - знаменитая труппа цирковых клоунов, известных во всем мире своими невероятными способностями втискивать неограниченное количество себя в даже самый маленький автомобиль. В межсезонье братья любят собираться на ежегодное собрание Конкортиционистов в местном парке. Братья ощущают трудности не только в отношении тесноты, но и в отношении денег, поэтому они пытаются найти способ привлечь всех к вечеринке, что сводит к минимуму количество миль, пройденных всеми автомобилями (таким образом, экономя газ, износ, амортизацию и т. д.). Для этого они готовы втиснуться в несколько автомобилей, необходимых для минимизации общего количества миль на всех своих автомобилях. Это часто приводит к тому, что один брат едет в дом другого брата, оставляет там свой автомобиль и пересаживается в автомобиль брата. Однако в парке есть ограничение: на стоянке на площадке для пикников может быть только ограниченное количество автомобилей, поэтому это следует учитывать при расчете. Кроме того, из-за оплаты въезда в парк, при прибытии в парк автомобиля любого брата, он должен там остаться; нельзя высадить пассажиров и поехать забрать других братьев. Ваша цирковая труппа должна решить эту непростую задачу, поэтому Вам остается написать программу для решения проблемы минимизации пройденных миль.

Входные данные

Первая строка содержит число n - количество дорог между братьями или между братьями и парком. Каждая из следующих n строк содержит описание дороги в виде name1 name2 dist, где name1 и name2 - имена двух братьев или имя брата и слово Park (в любом порядке), dist - расстояние между ними. Дороги являются двусторонними, dist всегда положительно. Максимальное количество братьев равно 20, наибольшая длина их имен содержит до 10 символов. За этими n строками следует последняя строка содержащая целое число s - количество машин, которое может поместиться на стоянке места для пикника. Считайте, что всегда существует путь от дома каждого брата до парка и что решение всегда существует.

Выходные данные

Выведите строку в виде

Total miles driven: xxx

где xxx - общее количество миль, пройденных всеми машинами братьев.