405047 - 野餐

马戏团的小丑们有一个特异功能，无论一个车子有多小，他们都能钻进去，也就是说，一辆车子能够容纳无限个小丑。 现在小丑们要去一个公园野餐，他们住在不同的地方，为了节约能源，要使得所有车子加起来走的路程最小，往往是几个小丑各自开车到另一个小丑家停车后，再挤在一辆车上开车到公园。 但是公园的停车位是有限制的，公园最多只能停k辆车。一旦某个小丑开车到了公园，那么就必须停在公园，不能再回去载其他小丑了。 求所有小丑开车的最短总路程。

第一行是一个整数n，表示小丑与小丑之间及与公园之间的连接数。以下n行表示从Ａ地到Ｂ地的路程数，路是双向的，小丑数不会超过20人，并且地名的字符长度不会超过10个字符。每一个小丑家到公园的路是连通的，不会出现无解的情况。最后一行是一个整数，表示公园可以容纳的车辆数。

最小路径数。