2425. Sub Version Network System

单点时限: 3.0 sec

内存限制: 256 MB

In 20XX, a epoch-making telecommunication system is invented. In this system, once this system is operated, it is possible to communicate permanently without cost, it does not depend on the distance nor amount of data. However, in this system, there are three different versions (1.0, 2.0 and 3.0) and a special conversion device is required in order to communicate between systems of different version. When the difference of the version is x , this device costs c * x2 to communicate between them. That is, communicating between version 1.0 and version 3.0 costs 4.0 * c, and communicating between version 2.0 and version 3.0 costs c.

ICPC (International Company of Portable Communications) is a global company and its branch offices are all over the world. ICPC decides to buy the telecommunication system and to set up in all branch offices to construct inter-office communication network. Now, ICPC should determine a version to set up at a branch office because different selection may lead different cost. The price for the system is different because of its version and country. Moreover, the system cannot transport another country.

Your job is to write a program to calculate the minimum cost of the entire system from given cost information and given information about communication between pairs of branch offices.

输入格式

Input consists of multiple test cases. The first line of each test case contains two positive integers n ( n <= 50 ), c (c <= 100,000) separated by single space character. The integer n indicates the number of countries with branch office of ICPC, and the integer c indicates initial cost for starting communication. Each branch offices are numbered from 1 to n. The following n lines contain 2 positive integers b1 and b2 ( b1 , b2 <= n , b1 != b2 ) separated by single space. These integers indicate information about a branch office b1 communicates to b2. Input is terminated by a case of n = c = 0, and it should not be processed.

You can assume that the total cost does not exceeds 10,000,000.

输出格式

For each test case, you should output the minimum cost.

样例

Input
1 1
1 2 3
0
4 1
10 20 30
10 20 30
10 20 30
10 20 30
3
1 2
2 3
2 4
4 100
0 99999 99999
99999 0 99999
99999 99999 0
0 99999 99999
3
1 2
2 3
2 4
0 0
Output
1
40
300

0 人解决,1 人已尝试。

0 份提交通过,共有 4 份提交。

9.9 EMB 奖励。

创建: 12 年,10 月前.

修改: 4 年前.

最后提交: 9 月,4 周前.

来源: International Maximum-Cup 2008

题目标签