U132410 最小代价

        某某通信公司接到了一项工程，要求实地考察。经过跋山涉水之后， 终于来到了入口处，初极狭，才通人。复行数十步，豁然开朗。         经考察发现，这片山区里面有n个村庄，通信公司需要让这n个村庄都 连接上网络。         使某一村庄C连接网络的方案有两种：         （1）在C建立一个网络中心。         （2）从有网络的村庄D拉一根网络光纤到C。 为了简化问题，我们做出如下约定：          （1）n个村庄的编号为1--n，每个村庄都有自己的坐标$（x_i，y_i）$，不同村庄的坐标有可能相同。          （2）每个村庄都有自己的一个连接花费值$k_i$。          （3）每个村庄都有自己的一个建造花费值$c_i$，为从编号为i的村庄建造一个网络中心所需要的花费。          （4）连接两个村庄$i，j$的光纤长度为$abs（x_i-x_j）+ abs(y_i-y_j)$          （5）连接两个村庄$i，j$的光纤每单位的花费值为$（k_i+k_j），k_i，k_j$为村庄$i$，$j$的连接花费值。

第一行输入一个正整数$n（n

输出一个整数$val$，表示使这些村庄都通网所需要的最小花费。

60%数据保证仅在1号村庄修建一个网络中心是最优的。 多组输入。