Teleportasiya (Gümüş)#10410

Teleportasiya (Gümüş)

1 saniyə

128 meqabayt

Çətin

Fermer Conun ən çox xoşlamadığı təsərrüfat işlərindən biri böyük miqdarda inək peyinini bir yerdən başqa yerə daşımaqdır. Bu prosesi asanlaşdırmaq üçün o, parlaq bir ixtira ilə çıxış edib: peyin teleportu! Peyini traktorunun arxasındakı araba ilə iki nöqtə arasında daşımaq əvəzinə, o, peyin teleportundan istifadə edərək peyini bir yerdən digərinə ani olaraq daşıya bilər.

Fermer Conun fermi tək uzun düz yol boyunca qurulub, buna görə də fermdəki istənilən yer sadəcə bu yol üzərindəki mövqeyi ilə təsvir oluna bilər (əslində, ədəd oxu üzərində bir nöqtə kimi). Teleportor iki $x$ və $y$ ədədi ilə təsvir olunur: $x$ yerinə gətirilən peyin dərhal $y$ yerinə daşınır.

Fermer Con, qurulacaq teleportorun birinci ucunu $x = 0$ x = 0 nöqtəsində qoymaq qərarına gəlib. Sizin vəzifəniz ona digər $y$ ucu üçün ən yaxşı mövqeyi seçməkdə kömək etməkdir. Dəqiq desək, onun fermasında $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) peyin yığını var. $i$ -ci yığın $a_{i}$ a_i mövqeyindən $b_{i}$ b_i mövqeyinə köçürülməlidir və Fermer Con hər yığını ayrıca daşıyır. $d_{i}$ d_i ilə Fermer Conun $i$ -ci yığını daşıyarkən peyinlə birlikdə traktorunu sürdüyü məsafəni işarə edək. Əgər o, $i$ -ci yığını birbaşa traktorla daşıyırsa, onda $d_{i} = ∣ a_{i} - b_{i} ∣$ d_i = |a_i - b_i|; əgər o, teleportordan istifadə edirsə (məsələn, yığını traktoru ilə $a_{i}$ a_i-dən $x$ -ə, sonra isə $y$ -dən $b_{i}$ b_i-yə daşıyaraq), $d_{i}$ d_i dəyəri daha kiçik ola bilər.

Fermer Cona $d_{i}$ d_i dəyərlərinin cəminin minimum mümkün qiymətini tapmaqda kömək edin, bunu teleportorun digər ucu olan $y$ -i optimal şəkildə seçməklə əldə edə bilər. Hər bir yığının daşınması üçün eyni $y$ mövqeyindən istifadə olunur.

Giriş

Birinci sətirdə $n$ tam ədədi verilir. Növbəti $n$ sətirdən hər birində iki tam ədəd $a_{i}$ a_i və $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) verilir. Bu qiymətlər mütləq fərqli olmaya bilər.

Çıxış

$d_{i}$ d_i dəyərlərinin cəminin minimum mümkün qiymətini çap edin. Nəzərə alın ki, bu ədəd standart $32$ -bitlik tam ədəd tipinə sığmaya bilər, buna görə də long long kimi $64$ -bitlik tam ədəd tipindən istifadə etməyiniz lazım ola bilər.

Nümunələr

Bu nümunədə $y = 8$ y = 8 təyin etməklə, Fermer Con $d_{1} = 2$ d_1 = 2, $d_{2} = 5$ d_2 = 5 və $d_{3} = 3$ d_3 = 3 əldə edə bilər. Qeyd edək ki, $y$ -in $[7, 10]$ aralığındakı istənilən qiyməti də optimal həlli verir.

Nümunə 1