Piknik planlaşdırılması

Братлар Конторсия - dünyaca məşhur sirk klounları truppasıdır, özlərini hətta ən kiçik avtomobilə belə yerləşdirmək bacarıqları ilə tanınırlar. Mövsümdən kənar dövrdə qardaşlar yerli parkda illik Konkorsionistlər toplantısına toplaşmağı sevirlər. Qardaşlar yalnız sıxlıqla deyil, həm də maliyyə ilə bağlı çətinliklər yaşayırlar, buna görə də hər kəsi partiyaya cəlb etməyin bir yolunu tapmağa çalışırlar ki, bu da bütün avtomobillərlə gedilən mil sayını minimuma endirir (beləliklə, yanacaq, aşınma, amortizasiya və s. qənaət edilir). Bunun üçün onlar bütün avtomobillərdə gedilən ümumi mil sayını minimuma endirmək üçün lazım olan bir neçə avtomobilə yerləşməyə hazırdırlar. Bu, tez-tez bir qardaşın digər qardaşın evinə getməsi, orada avtomobilini qoyması və qardaşının avtomobilinə minməsi ilə nəticələnir. Lakin parkda bir məhdudiyyət var: piknik sahəsinin dayanacağında yalnız məhdud sayda avtomobil ola bilər, buna görə də bu hesablamada nəzərə alınmalıdır. Bundan əlavə, parkın giriş haqqı səbəbindən, hər hansı bir qardaşın avtomobili parka gəldikdə, orada qalmalıdır; sərnişinləri düşürüb digər qardaşları götürmək üçün gedə bilməz. Sizin sirk truppanız bu çətin məsələnin həllini tapmalıdır, buna görə də sizə gedilən millərin minimallaşdırılması problemini həll etmək üçün proqram yazmaq qalır.

Giriş məlumatları

Birinci sətir qardaşlar arasında və ya qardaşlar və park arasında yolların sayını göstərən n ədədini ehtiva edir. Növbəti n sətirin hər biri name1 name2 dist şəklində yol təsvirini ehtiva edir, burada name1 və name2 iki qardaşın adları və ya bir qardaşın adı və Park sözü (istənilən ardıcıllıqla), dist isə onların arasındakı məsafədir. Yollar ikitərəflidir, dist həmişə müsbətdir. Maksimum qardaş sayı 20-dir, adlarının ən uzunluğu 10 simvola qədərdir. Bu n sətirdən sonra son sətir piknik sahəsinin dayanacağında yerləşə biləcək avtomobillərin sayını göstərən tam s ədədini ehtiva edir. Hər bir qardaşın evindən parka yolun olduğunu və həmişə həllin mövcud olduğunu qəbul edin.

Çıxış məlumatları

Aşağıdakı formada bir sətir çıxarın

Total miles driven: xxx

burada xxx qardaşların bütün avtomobilləri ilə gedilən ümumi mil sayıdır.