3368: Just a Cost Problem

 在一条河的两岸有M家公司，每家公司有N个计算中心，政府决定沿河修建若干个网点，以方便各公司共享数据，每个公司都可以有一个连接点，并将自己公司的所有计算中心直接连到自己公司的连接点上，这个费用由公司出，之后政府再将各个连接点连起来，这个费用由政府出。由于每个公司的N个计算中心位置可能各不相同，而这些计算中心又必须与自己的公司的连接点直接相连，所以每个公司都会确定一个使自己需要线路最少的连接点。之后，由于政府也想减少花费，所以政府也会确定一种方法，使得所有公司的连接点直接或间接地连起来而且花费最少。

     在一个二维直角坐标系上，我们可以假设河两岸分别为直线 L：y=1 和直线 P: y=-1,

    对于编号为奇数的公司，这个公司的连接点只能在直线L上，对于编号为偶数的公司，这个公司的连接点只能直线P上。公司确定一个连接点的位置后，将自己的所有计算中心直接与这个连接点相连。

输入有多组测试数据，对于每一组测试数据：

第一行：一个正整数M，表示公司数目，M<=20000;

接下有M组公司的数据：

第一行：一个正整数N，表示公司的计算中心数目，N<=6;

接下来N行，每行都是两个整数x 和y,表示公司各个计算中心的位置。

对于每组测试数据，输出两行：

第一行：所有公司花费的最小的线路总长,只输出结果的整数部分,小数部分全部舍去。

8
1
328360 799448
3
142697 -881120
-719650 -801090
-525480 396220
3
-742072 -654462
-852355 658106
68761 320230
1
-154278 790640
6
-209603 539002
-87586 -998520
-152948 373821
425320 -871174
499196 -462450
-989578 301809
2
753778 407965
258352 677532
2
-395325 -118567
620950 -158760
2
273464 18676
217800 451588

13356635
1047765