Brandon is cleaning his room. He has identical-looking pusheens lying in various locations on the room. No two pusheens are at the same location.
One day, Brandon draws a line cutting his room perfectly in half. He wants to arrange the pusheens in a way where, if there is a pusheen at some location where , there is a different pusheen at . This is unnecessary, of course - Brandon doesn't have to arrange his pusheens in this fashion. However, he feels forced to arrange his pusheens in this way. If someone accidentally trashes one of his pusheens, he will be able to reconstruct where the pusheen goes. Of course, if a pusheen is on the line , then the location cannot be reconstructed exactly, but this is not a critical situation.
Brandon is very lazy, so moving a pusheen from to requires effort equal to . Compute the minimum sum of efforts Brandon must exert in order to achieve his desired balanced pusheen layout.
It is not permitted to have more than one pusheen at any given point.
No two pusheens will start at the same point.
The first line contains a single positive integer, .
The next lines each contain two space-separated integers, and , indicating the location of the th pusheen.
Output the minimum effort Brandon must exert. Your answer will be considered correct if it has absolute or relative error of at most when compared with the reference answer.
Sample Input 1
2 -1 1 2 2
Sample Output 1
Sample Input 2
3 -1 39 1 39 2 3
Sample Output 2