Телепортация (Gümüş)
Fermer Ceyhun fermada peyin qablarını təmizləməkdən ən çox nifrət edir. Bu işi asanlaşdırmaq üçün peyin teleportu icad edib. Artıq peyini traktorun arxasında arabada daşımaq əvəzinə, teleport vasitəsilə bir yerdən başqa yerə köçürə bilər.
Ceyhun'un ferması uzun bir düz yol boyunca yerləşir, belə ki, fermadakı hər hansı bir yer bu yoldakı mövqeyi ilə təsvir edilə bilər (rəqəmsal düz xətt üzərində nöqtə kimi). Teleport iki ədəd x və y ilə təsvir edilir, bu da peyinin x nöqtəsindən dərhal y nöqtəsinə teleport edilə biləcəyini göstərir.
Ceyhun teleportun ilk son nöqtəsini x = 0 olaraq təyin edib. Sizin vəzifəniz onun üçün digər son nöqtə y üçün ən yaxşı seçimi müəyyən etməkdir. Xüsusilə, fermada n (1 ≤ n ≤ 10^5) peyin qabı var. i-ci qabı a[i] mövqeyindən b[i] mövqeyinə köçürmək lazımdır və Ceyhun hər qabı ayrı-ayrılıqda daşıyır. d[i] hər qabın daşınması üçün lazım olan məsafəni göstərir. d[i] teleportdan istifadə edildikdə potensial olaraq daha az ola bilər (traktorla a[i]-dən x-ə və sonra y-dən b[i]-ə daşımaqla).
Ceyhun'a y (teleportun ikinci ucu) dəyərini düzgün seçməklə əldə edə biləcəyi minimal mümkün d[i] cəmini müəyyən etməyə kömək edin. Eyni y dəyəri bütün qabların daşınması üçün istifadə olunur.
Giriş məlumatları
Girişin ilk sətiri n ədədini ehtiva edir. Sonrakı n sətirin hər biri a[i] və b[i] olmaqla iki tam ədəd ehtiva edir, -10^8...10^8 intervalında. Bütün dəyərlər mütləq fərqli deyil.
Çıxış məlumatları
Bir ədəd çıxarın - Ceyhun'un əldə edə biləcəyi minimal d[i] cəmi. Qeyd edək ki, bu ədəd 32-bit tam ədədi keçə bilər, buna görə daha böyük məlumat növü istifadə edilməlidir, məsələn, C/C++-da "long long".
Nümunə
Bu nümunədə y = 8 seçərək Ceyhun d[1] = 2, d[2] = 5, d[3] = 3 əldə edə bilər. Qeyd edək ki, [7, 10] intervalında olan hər hansı y dəyəri də optimal həlli dəstəkləyir.