U369000 [HDU - 3516] Tree Construction

Consider a two-dimensional space with a set of points $(x_i, y_i)$ that satisfy $x_i < x_j$ and $y_i > y_j$ 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.

The input begins with a line that contains an integer $n$ $(1 \le n \le 1000)$, the number of points. Then $n$ lines follow. The $i$-th line contains two integers $x_i$ and $y_i$ $(0 \le x_i, y_i \le 10000)$, which give the coordinates of the $i$-th point.

Print the total length of edges in a line.