描述

“柔体兄弟”是一群著名的马戏团小丑，他们以能够在极小的车辆中塞进数量不受限制的成员的惊人能力而闻名于世。在淡季期间，这些兄弟喜欢在当地的公园举行年度柔体演员聚会。然而，这些兄弟不仅在狭小的空间方面很“紧凑”，在金钱方面也很“吝啬”，所以他们试图找到一种方法，让每个人都能参加聚会，同时使他们所有汽车行驶的总英里数最小化（这样可以节省汽油、减少车辆磨损等）。为此，他们愿意尽可能地将自己塞进最少数量的汽车中，以最小化所有汽车行驶的总英里数。这通常会导致许多兄弟开车到某个兄弟的家，留下除一辆车之外的所有车，然后都挤进剩下的那辆车。不过，公园有一个限制：野餐地点的停车场只能容纳有限数量的汽车，所以在整体的“吝啬计算”中必须考虑到这一点。此外，由于公园有入场费，一旦任何兄弟的汽车到达公园，它就会停在那里；他不会放下乘客然后离开去接其他兄弟。对于普通的马戏团家族来说，解决这个问题是一个挑战，所以现在要你编写一个程序来解决他们的最小里程问题。

输入

输入将由一个问题实例组成。第一行将包含一个整数 n，表示兄弟之间或兄弟与公园之间的高速公路连接数量。接下来的 n 行将每行包含一个连接，格式为 name1 name2 dist，其中 name1 和 name2 要么是两个兄弟的名字，要么是“Park”（公园）和一个兄弟的名字（顺序任意），dist 是它们之间的整数距离。这些道路都是双向的，并且 dist 总是正数。兄弟的最大数量为 20，任何名字的最大长度为 10 个字符。在这 n 行之后，将有最后一行包含一个整数 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 79
Park Herb 24
Herb Eduardo 79
3

输出数据 1

Total miles driven: 183

来源

2000 年中东部北美赛