22607번 - 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.

Figure 1: 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 ≤ n ≤ 1000), the number of points. Then n lines follow. The i-th line contains two integers x_i and y_i (0 ≤ x_i, y_i ≤ 10000), which give the coordinates of the i-th point.

Print the total length of edges in a line.