吉与鸡:叫个鸡吧

Time Limit: 1s

Memory Limit: 65536kb

Description

  吉吉们生活在一个神奇的吃鸡国。这个国家有个城市,每个城市的吉吉们都很喜欢吃鸡,但是把自己城市的鸡都吃腻了,所以要叫别的城市的鸡。每个城市的鸡对应一个美味度,并且每个城市的吉吉们有一个饥渴度。由于鸡在运送的过程中会损失一定的美味,所以城市能让城市满足的饥渴度为。其中表示城市之间的距离。两个城市的距离为其之间的直线距离。一个城市的吉吉们能满足,当且仅当其他所有城市对其贡献之和大于等于其饥渴度,即

  曾经,每个城市的鸡都非常美味,所以吉吉们天天都吃鸡,过着幸福的生活。

  但是,吉吉们实在是吃腻了自己城市的鸡,所以对自己城市的鸡产生了厌恶,厌恶度为,其中为厌恶系数。也就是说,别人越想吃的鸡,自己就越不想吃。

  而你,作为这个吃鸡国度的神,要分配每个城市的鸡的美味度,使得在每个城市都能满足的情况下,所有城市对自己的鸡的厌恶度的总和最小。输出最小的厌恶度之和。

Input

  输入的第一行包含一个整数,表示有T组测试数据。

  对于每个测试数据,第一行包含一个整数,表示有个城市。

  接下来输入行,每行两个整数,表示个城市的坐标。

  接下来一行有个浮点数,表示个城市饥渴度

  接下来一行有个浮点数,表示个城市厌恶系数

Output

  对于每个测试数据,输出一行,为厌恶度的总和,保留三位小数。

Sample Input

1
3
0 0
1 2
2 1
1 1 1
1 1 1

Sample Output

2.704

Hint

None

Source

None

提交代码