Feeding the Cats

Interview

Time limit1sMemory limit256 MB

Summary

Starting at (0,0), visit all N cats on a grid, moving in Manhattan steps, and return to (0,0) in the shortest time.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Shortest path, Greedy
Solved: No attempts yet

Problem

Yunseong is a cat feeder at Konkuk University who would not take second place to anyone, but he is ashamed of being one. He likes cats more than anyone else does, so why does he hide his true feelings?

Yunseong does not want anyone to find out that he feeds the cats on campus, so he wants to take the shortest possible route to feed all the cats and come back.

The school can be represented as a two-dimensional plane. Yunseong can move one cell up, down, left, or right, and each cell of movement takes 1 second. He must move to the coordinates where a cat is located to feed it, and since he is cool and just leaves after feeding, feeding a cat takes no time.

Yunseong stands at the school's only gate, whose coordinates are (0,0). After feeding all the cats, he must return to this gate.

What is the minimum number of seconds in which Yunseong can feed all the cats and leave?

Input

The first line gives the number of cats N (1 ≤ N ≤ 16). The next N lines give the coordinates X, Y of a cat, separated by a space. (0 ≤ X, Y ≤ 1,000,000)

Output

On the first line, print the time in seconds taken to start at (0,0), feed all the cats, and return to (0,0).

Examples2

Example 1
Input
```
5
0 4
1 0
1 2
2 4
3 1
```
Expected output
```
16
```
Example 2
Input
```
2
0 1
1 0
```
Expected output
```
4
```