#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Consider a two-dimensional space with a set of points (xi, yi) that satisfy xi < xj and yi > yj for all i < j. We want to have them all connected by a directed tree whose edges go toward either right (x positive) or upward (y positive). The figure below shows an example tree.

Write a program that finds a tree connecting all given points with the shortest total length of edges.

## Limits

For all testcases, 0 ≤ X_{i}, Y_{i} ≤ 10^{9}.

Subtask 1 (23%): 1 ≤ N ≤ 50.

Subtask 2 (25%): 1 ≤ N ≤ 500.

Subtask 3 (52%): 1 ≤ N ≤ 5000.

Subtask 4 (0%): Sample Testcases.

## Input

The input begins with a line that contains an integer N, the number of points.

Then N lines follow. The i-th line contains two integers X_{i}and Y

_{i}, which give the coordinates of the i-th point.

## Output

Print the total length of edges in a line.

## Sample Testcase 1

### Input

5 1 5 2 4 3 3 4 2 5 1

### Output

12

## Sample Testcase 2

### Input

1 10000 0

### Output

0

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 23 | 22 | 5s | 512MB | Minimum |

2 | 25 | 42 | 5s | 512MB | Minimum |

3 | 52 | 62 | 5s | 512MB | Minimum |

4 | 0 | 2 | 5s | 512MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o treeconstruction -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512