Teletransportación (Plata)#10410

Teletransportación (Plata)

1 segundo

128 megabytes

Difícil

Una de las tareas agrícolas que menos le gustan al Granjero John es transportar grandes cantidades de estiércol de vaca. Para agilizar este proceso, ha ideado un invento brillante: ¡el teletransportador de estiércol! En lugar de transportar el estiércol entre dos puntos en un carro detrás de su tractor, puede usar el teletransportador de estiércol para transportar el estiércol instantáneamente de un lugar a otro.

La granja del Granjero John está construida a lo largo de un único camino recto largo, por lo que cualquier ubicación en la granja puede describirse simplemente por su posición a lo largo de este camino (en efecto, un punto en la recta numérica). Un teletransportador se describe mediante dos números $x$ e $y$ : el estiércol llevado a la posición $x$ puede ser transportado instantáneamente a la posición $y$ .

El Granjero John ha decidido construir un teletransportador con su primer extremo en $x = 0$ x = 0. Tu tarea es ayudarlo a elegir la mejor posición para el otro extremo $y$ . Específicamente, hay $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) montones de estiércol en su granja. El $i$ -ésimo montón debe moverse de la posición $a_{i}$ a_i a la posición $b_{i}$ b_i, y el Granjero John transporta cada montón por separado. Sea $d_{i}$ d_i la distancia que el Granjero John conduce su tractor con estiércol mientras transporta el $i$ -ésimo montón. Si transporta el $i$ -ésimo montón directamente con el tractor, entonces $d_{i} = ∣ a_{i} - b_{i} ∣$ d_i = |a_i - b_i|; si usa el teletransportador (por ejemplo, llevando el montón con su tractor desde $a_{i}$ a_i hasta $x$ y luego desde $y$ hasta $b_{i}$ b_i), $d_{i}$ d_i puede resultar menor.

Ayuda al Granjero John a determinar la mínima suma posible de los valores $d_{i}$ d_i que puede lograr colocando el otro extremo $y$ del teletransportador en una posición óptimamente elegida. La misma posición $y$ se utiliza para transportar cada montón.

Entrada

La primera línea contiene el entero $n$ . Cada una de las siguientes $n$ líneas contiene dos enteros $a_{i}$ a_i y $b_{i} (- 1 0^{8} \leq a_{i}, b_{i} \leq 1 0^{8})$ b_i~(-10^8 \le a_i, b_i \le 10^8). Estos valores no son necesariamente distintos.

Salida

Imprime un entero — la suma mínima de los valores $d_{i}$ d_i que el Granjero John puede lograr. Ten en cuenta que este número puede no caber en un tipo entero estándar de $32$ bits, por lo que podrías necesitar un tipo entero de $64$ bits como long long en C/C++.

Ejemplos

En este ejemplo, al establecer $y = 8$ y = 8, el Granjero John puede lograr $d_{1} = 2$ d_1 = 2, $d_{2} = 5$ d_2 = 5 y $d_{3} = 3$ d_3 = 3. Observa que cualquier valor de $y$ en el rango $[7, 10]$ también produce una solución óptima.

Ejemplo 1