Long long Catfish#4356

Long long Catfish

15 seconds
256 megabytes
Easy

Catfish Ivan really is the longest fish in the department. Perhaps, therefore, he isn't interested in sitting at a desk in the same position as the others. He loves to lay on them. Ivan chose desks on which he wants to lay today. Movement in the audience is only possible between the rows of desks, that means, that the distance between the desk, located at the point (x_1, y_1) and a desk at the point (x_2, y_2), equals |x_1-x_2| + |y_1-y_2|. The audience is large, so Ivan wants to minimize the total distance required to visit all desks. He can start his journey from anywhere in the audience.

Input

The first line contains the number of desks (1 \le N \le 20), on which Ivan wants to lay today. Each of the next lines contains two integers x_i, y_i (1 \le x_i, y_i \le 10^{10}) - the coordinates of desks.

Output

The minimum distance that Ivan needs to travel.

Examples

Example 1

Loading
Loading