Teletrasporto (Silver)#10410

Teletrasporto (Silver)

1 secondo

128 megabyte

Difficile

Una delle faccende agricole che a Farmer John piacciono di meno è trasportare in giro grandi quantità di letame bovino. Per snellire questo processo, ha avuto un'idea geniale: il teletrasportatore di letame! Invece di trasportare il letame tra due punti con un carrello trainato dal trattore, può usare il teletrasportatore di letame per spostare il letame istantaneamente da una posizione a un'altra.

La fattoria di Farmer John è costruita lungo un'unica lunga strada diritta, quindi qualsiasi posizione nella fattoria può essere descritta semplicemente dalla sua posizione lungo questa strada (in pratica, un punto sulla retta numerica). Un teletrasportatore è descritto da due numeri $x$ e $y$ : il letame portato nella posizione $x$ può essere trasportato istantaneamente nella posizione $y$ .

Farmer John ha deciso di costruire un teletrasportatore con il primo estremo in $x = 0$ x = 0. Il tuo compito è aiutarlo a scegliere la posizione migliore per l'altro estremo $y$ . Nello specifico, ci sono $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) cumuli di letame nella sua fattoria. Il cumulo $i$ -esimo deve essere spostato dalla posizione $a_{i}$ a_i alla posizione $b_{i}$ b_i, e Farmer John trasporta ciascun cumulo separatamente. Sia $d_{i}$ d_i la distanza che Farmer John percorre con il trattore mentre trasporta il cumulo $i$ -esimo. Se trasporta direttamente il cumulo $i$ -esimo con il trattore, allora $d_{i} = ∣ a_{i} - b_{i} ∣$ d_i = |a_i - b_i|; se usa il teletrasportatore (per esempio, trasportando il cumulo con il trattore da $a_{i}$ a_i a $x$ e poi da $y$ a $b_{i}$ b_i), $d_{i}$ d_i potrebbe risultare più piccolo.

Aiuta Farmer John a determinare la minima somma possibile dei valori $d_{i}$ d_i che può ottenere posizionando in modo ottimale l'altro estremo $y$ del teletrasportatore. La stessa posizione $y$ viene usata per trasportare ogni cumulo.

Input

La prima riga contiene l'intero $n$ . Ciascuna delle successive $n$ righe contiene due interi $a_{i}$ a_i e $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). Questi valori non sono necessariamente distinti.

Output

Stampa un intero — la minima somma dei valori $d_{i}$ d_i che Farmer John può ottenere. Nota che questo numero potrebbe non stare in un normale tipo intero a $32$ bit, quindi potrebbe essere necessario usare un tipo intero a $64$ bit come long long in C/C++.

Esempi

In questo esempio, impostando $y = 8$ y = 8, Farmer John può ottenere $d_{1} = 2$ d_1 = 2, $d_{2} = 5$ d_2 = 5 e $d_{3} = 3$ d_3 = 3. Nota che anche qualsiasi valore di $y$ nell'intervallo $[7, 10]$ produce una soluzione ottimale.

Esempio 1