Forming Quiz Teams

You have been given the job of forming the quiz teams for the next “MCA CPCI Quiz Championship”. There are 2N students interested in participating and you have to form N teams, each team consisting of two members. Since the members have to practice together, all the students want their teammate's house as near as possible. Let x₁ be the distance between the houses of the members of team 1, x₂ be the distance between the houses of the members of team 2, and so on. You have to make sure the summation (x₁ + x₂ + x₃ + … + x_N) is minimized.

Input Specification

There will be several test cases in the input. Each test case starts with an integer N (N ≤ 8). The next 2N lines will give the information of the students. Each line starts with the student's name, followed by the x-coordinate and then the y-coordinate. Both x and y are integers in the range 0 to 1000. Students' names will consist of lowercase letters only, and their lengths will be at most 20.

The input is terminated by a case where N is equal to 0.

Output Specification

For each test case, output the case number followed by the summation of the distances, rounded to 2 decimal places. Follow the sample output for the exact format.

Sample Input

1. 5
2. sohel 10 10
3. mahmud 20 10
4. sanny 5 5
5. prince 1 1
6. per 120 3
7. mf 6 6
8. kugel 50 60
9. joey 3 24
10. limon 6 9
11. manzoor 0 0
12. 1
13. derek 9 9
14. jimmy 10 10
15. 0

download as text file

Output for Sample Input

1. Case 1: 118.40
2. Case 2: 1.41

download as text file