A well-known programming contest is considering a new way to position its teams. For the contest all teams have to be assigned some position in an infinitely-large gym hall. To keep a good overview of the teams the following strategy is chosen:
All teams have been assigned a unique integer ID in the range . Any two teams with IDs and , where , must be placed at positions , , such that and .
Unfortunately, someone already assigned the fixed internet access point for each team. The access points are quite big and only have one port, so access points for different teams are located at different positions. Every team must be connected to its designated access point by a direct UTP cable. The cost of a UTP cable of length is .
Find a placement for all teams, such that their respective order along both axes is maintained and the total cost of the required UTP cables is minimised. As the judges are not too worried about privacy, they are fine with two or more teams being placed at the exact same location or being arbitrarily close together. See the figure for an example.
:::align{center}
:::
输入格式
The input consists of:
One line with one integer (), the number of teams.
lines, the th of which contains two integers (), the location of the internet access point of team .
No two access points are at the same position.
输出格式
Output the minimum total cost of all UTP cables required to connect the teams to their access points in an optimal legal layout.
Your answer should have an absolute or relative error of at most .
