Rectangles

Time limit1sMemory limit128 MB

Summary

Choose an orientation (width/height swap) for each rectangle placed side by side to maximize the sum of top and internal vertical edges excluding outer sides and bottoms.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Implementation
Solved: No attempts yet

Problem

You are given n rectangles, numbered from 1 to n. Place them on the x-axis in order of their numbers, from left to right, packed tightly against one another with no gaps. Each rectangle may be stood up so that either its shorter side or its longer side rests on the ground (the x-axis).

Choose an orientation for every rectangle so that the total "top perimeter" of the whole figure is as long as possible. The top perimeter is the sum of the lengths of all outline edges except the bottom edges lying on the x-axis and the two outermost vertical sides (the far-left and far-right sides).

Write a program that computes the maximum possible top perimeter.

Input

The first line contains the number of rectangles n. Each of the next n lines contains two integers ai and bi, the lengths of the two sides of the i-th rectangle. (0 < n < 1000; 0 < ai < bi < 1000)

Output

Print the maximum top perimeter as a single integer.

Hint

The figure above shows one example arranged so that the top perimeter is maximized. The edges included in the top perimeter are DC, CG, GF, FJ, JI, IM, ML, LP, PO, whose lengths sum to 68.

Examples3

Example 1
Input
```
5
2 5
3 8
1 10
7 14
2 5
```
Expected output
```
68
```
Example 2
Input
```
1
3 7
```
Expected output
```
7
```
Example 3
Input
```
2
1 2
1 2
```
Expected output
```
4
```