Tree Construction
시간 제한2초메모리 제한512 MB
x가 커지면 y가 작아지는 순서로 주어진 점들을 오른쪽이나 위쪽 방향 간선으로 모두 연결할 때, 간선 길이 합의 최솟값을 구한다.
문제
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.
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 xi and yi (0 ≤ xi, yi ≤ 10000), which give the coordinates of the i-th point.
출력
Print the total length of edges in a line.