408863: GYM103366 C Crystal Caves

One morning, Cirno woke up drowsy Daiyousei very early, and pointed out not far away with excitement.

「Hurry up, I heard, Under the ice there hides ancient relics」

「Wumm......」

As everyone knows, In Gensokyo, Rumors are the truth. Beside the ancient relics, there also buries a gem with incredible magic -「Cristal of Cyan Heart」. However, what connecting the ice and relics is a large crystal cave.

Crystal caves contain $$$n$$$ floors, and the floor near the ground is the narrowest. So we call it the first floor. After that, each floor is more spacious than the previous floor.

Abstractly, we define that the $$$y$$$-axis of $$$i$$$-th floor is $$$-i$$$, and the $$$x$$$-axis of it can be described with a closed interval $$$[l_i,r_i]$$$ ( $$$l_i<l_{i-1}<r_{i-1}< r_i$$$ ). Moreover, The ground is $$$[l_0,r_0]=[0,0]$$$.

In order to break the boundary between the present world and the relics, Cirno should draw support from the magic of crystal in the caves.

Specifically, she will choose a location on each floor of the crystal cave to activate crystal. Then the total magic value is the sum of Manhattan distances between all pairs of activated crystals.

To be on the safe side, Cirno decides to maximize the magic value.

And you are arranged to calculate the maximum of magic value to help her.

The first line contains only one integer $$$n$$$.

And in the following $$$n$$$ lines, each line contains two integers representing $$$l_i, r_i$$$, separated by blank.

$$$1\le n \le 2000$$$，$$$-10^9<l_n<\cdots<l_1<0<r_1<\cdots<r_n<10^9$$$.

The output contains one number that representing the answer.

3
-4 2
-6 4
-9 6

30

4
-3 3
-6 5
-7 8
-9 9

70

Sample 1

Dashed outline represent the section of crystal caves, and the black segments mean the region where Cirno can active crystals.

One of the Optimal placement scheme is marked by blue points.