You have been given the job of forming the quiz teams for the next MCA CPCI Quiz Championship. There are \(n = 2k\) students interested to participate and you have to form \(k\) teams, each team consisting of two members. Since the members have to practice together, all the students want their members house as near as possible. Let \(x_1\) be the distance between the houses of group 1, \(x_2\) be the distance between the houses of group 2 and so on. You have to make the groups so that \(x_1 + x_2 + \ldots + x_{k}\) is minimized.

Example:

The following image shows the first sample test case where \(n = 4\) and having student houses at positions \((1, 1), (1, 3), (6, 8)\) and \((8, 6)\). If we pair the students as shown in blue we get the minimum total distance. The orange pairing shows another possible pairing which is not optimal.

Input

• One line with one integer \(n\) giving the number of students.
• \(n\) lines each with two integers \(x_i, y_i\) giving the coordinates of the students houses.

Output

One line with a number giving the minimum total distance if we pair the students in an optimal way.

Limits

• \(n = 2k\) where \(1 \leq k \leq 8\)
• \(0 \leq x_i, y_i \leq 1000\)

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2

Sample input 3

Sample output 3

Sample input 4

Sample output 4