“扭曲兄弟”是一组著名的马戏团小丑，以其令人难以置信的能力将无限数量的自己塞进甚至最小的车辆而闻名于世。在淡季期间，兄弟们喜欢聚在一起参加当地公园的年度柔术运动会。然而，兄弟们不仅在空间方面很会节约，对钱也是一样的，所以他们试图找到让每个人都参加派对的方式，并且要最大限度地减少所有车辆行驶的总里程数（从而节省燃气、日常开支等）。为此，他们愿意将自己塞进尽可能少的汽车中，以尽量减少总里程数。这往往导致许多兄弟开车到一个兄弟的房子，除了一辆车外，其余车辆都留在原地。然而，公园有一个限制：野餐场地的停车场只能容纳数量有限的汽车，因此必须将其纳入整体计算的限制条件。此外，由于公园入场费，一旦兄弟的车到达公园，它就在那里，即它不会放下乘客后离开再去接其他兄弟。请你写一个程序来解决这个最小化总里程的问题。

输入描述

输入将包含一个问题实例：

1. 第一行将包含一个整数n，表示兄弟之间或兄弟与公园之间的高速公路连接数。
2. 接下来的n行，每行一个连接，格式为name1 name2 dist，其中name1和name2是两个兄弟的名字，或者其中一个是"Park"（公园），dist是两点之间的整数距离。道路均为双向，dist始终为正。兄弟的最大数量为20，任意名称的最大长度为10个字符。
3. 最后一行包含整数s，表示野餐场地停车场最多可容纳的车辆数。

题目保证从每个兄弟的房子到公园都有路径，且每个问题实例都有解决方案。

输出描述

输出一行，格式如下：

Total miles driven: xxx

其中xxx为所有兄弟车辆行驶的总里程数。

输入样例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

输出样例1

Total miles driven: 183