Parallelograms

We are given N parallelograms, numbered from 1 to N. Each parallelogram i has dimensions ~X_i~ and ~Y_i~ respectively. We want to arrange the parallelograms along the X-axis adjacent to each other without changing the order in which they are given. However, we can choose which side of each parallelogram to place along the X-axis in order to maximize the length of the upper polygonal line of the shape. The upper polygonal line of the resulting shape is defined as the perimeter of the shape, subtracting the left, right, and bottom sides. For example, in the diagram below, the upper polygonal line is defined by the straight segments DC, CG, GF, FJ, JI, IM, ML, LP, PO.

Input:

The first line of input contains a positive integer N, the number of parallelograms that will be given to us. This is followed by N lines, the i-th of which consists of two positive integers ~X_i~ and ~Y_i~, the dimensions of the i-th parallelogram. Consider that 1 ~\le X_i \le~ 1000 and 1 ~\le Y_i \le~ 1000.

Output:

Print a positive integer: the maximum length of the upper polygonal line that can result from any possible arrangement of the parallelograms on the x-axis.

Note: All data is read from standard input and printed to standard output.

Constraints:

• For subtasks worth 35% of total score, it holds:
  1 ~\le~ N ~\le~ 20
• For subtasks worth 100% of total score, it holds:
  1 ~\le~ N ~\le~ 100000

Example of Input - Output Files:

STDIN

5
2 5
3 8
1 10
7 14
2 5

STDOUT

68

Explanation of the example:

This example corresponds to the diagram in the problem statement. The arrangement that gives the maximum possible length of the upper polygonal line is the one shown in the diagram. As mentioned above, this polygonal line consists of the straight segments DC, CG, GF, FJ, JI, IM, ML, LP, PO with a total length of 5 + 6 + 3 + 7 + 10 + 13 + 7 + 12 + 5 = 68.