Score : 300 points
There are N balls in a two-dimensional plane. The i-th ball is at coordinates (x_i, y_i).
We will collect all of these balls, by choosing two integers p and q such that p \neq 0 or q \neq 0 and then repeating the following operation:
Find the minimum total cost required to collect all the balls when we optimally choose p and q.
Input is given from Standard Input in the following format:
N x_1 y_1 : x_N y_N
Print the minimum total cost required to collect all the balls.
2 1 1 2 2
1
If we choose p = 1, q = 1, we can collect all the balls at a cost of 1 by collecting them in the order (1, 1), (2, 2).
3 1 4 4 6 7 8
1
If we choose p = -3, q = -2, we can collect all the balls at a cost of 1 by collecting them in the order (7, 8), (4, 6), (1, 4).
4 1 1 1 2 2 1 2 2
2