|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
ACM 2016 - Round #2Ended |
C - Construyendo Arbol
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Se tiene una serie de puntos en el plano ($x_i$,$y_i$) que satisfacen $x_i < x_j$ y $y_i > y_j$ para todo $i<j$. Se quiere conectarlos por un árbol dirigido cuyas aristas siempre van para la derecha o para arriba y son paralelas a los ejes de coordenadas como se muestra en la figura:
Su tarea es escribir un programa calcule la menor longitud total de las aristas de un árbol que conecte los puntos como se explicó anteriormente.
Input
La entrada empieza con una línea que contiene un entero $n (1 \leq n \leq 1000)$ que representa la cantidad de puntos. Luego habrá $n$ líneas y en la línea $i$-esima habrá dos enteros $x_i$, $y_i$ $(0 \leq x_i,y_i \leq 10000)$ que representan las coordenadas del $i$-esimo punto.
Output
La salida debe contener una línea con un entero que sea la respuesta al problema.
Sample test(s)
Input
5
1 5
2 4
3 3
4 2
5 1
Output
12
Input
1
10000 0
Output
0