「Codeforces 70E」Information Reform
题目链接：Codeforces 70E
虽然已经是二十一世纪了，但是大众传媒在海象国并不普及，城市之间只能通过公路交流。海象国中任意两座城市之间有且只有一条路径，且每条道路的长度都是 $1$。
为了进行改革，将会选择一些城市作为信息中心，维护一个信息中心需要 $k$ 元钱。对于其他城市，他们将会从最近的信息中心获得消息，如果设两者直接的距离为 $len$，那么这将花费 $d_{len}$ 元钱。
请你求出一种方案使得花费最小，并求出每个城市会从哪个信息中心获得消息。
数据范围：$1\le n\le 180$，$1\le k\le 10^5$，$0\le d_i\le d_{i+1}\le 10^5$。