题目描述

一群小丑演员可以无限量地挤在同一辆车里。他们要从各自的家出发前往公园（公园名为 Park）。
公园的停车场容量有限，最多只能停放 $s$ 辆车（即最多 $s$ 辆车进入公园停车）。
一旦一辆车进入公园，就必须停在公园，不能再出去接其他人。

他们可以选择一些人开车到另一个人的家，然后所有人挤进一辆车，再继续前进。目标是使所有汽车行驶的总里程数最少，且所有人都到达公园。

输入给出若干人和公园之间的道路（双向），道路长度为正整数。
人数不超过 $20$，名字是不超过 $10$ 个字符的字符串，公园固定叫 Park。
保证每个人的家都有一条通往公园的道路。

输入格式

第一行一个整数 $n$，表示道路数量。
接下来 $n$ 行，每行两个字符串 $A, B$ 和一个整数 $L$，表示 $A$ 和 $B$ 之间有一条长度为 $L$ 的道路。
道路可能连接两个人，也可能连接一个人和公园（Park）。
最后一行一个整数 $s$，表示公园最大停车数量（即最多允许 $s$ 辆车进入公园）。

输出格式

输出一行：Total miles driven: xxx，其中 xxx 是最少总行驶里程。

数据范围

• 道路数量 $n$ 无明确上限，但人数 ≤ 20
• $1 \le L \le 200$
• $s \ge 1$

输入样例

10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3

输出样例

Total miles driven: 183