Işınlanma (Gümüş)#10410

Işınlanma (Gümüş)

1 saniye

128 megabayt

Zor

Çiftçi John'un en sevmediği çiftlik işlerinden biri, büyük miktarlarda inek gübresini bir yerden bir yere taşımaktır. Bu süreci kolaylaştırmak için harika bir icat ortaya koymuştur: gübre ışınlayıcısı! Gübreyi traktörünün arkasındaki bir arabayla iki nokta arasında taşımak yerine, gübre ışınlayıcısını kullanarak gübreyi bir konumdan diğerine anında aktarabilir.

Çiftçi John'un çiftliği tek bir uzun düz yol boyunca kuruludur, bu yüzden çiftlikteki herhangi bir konum, bu yol üzerindeki konumuyla basitçe tanımlanabilir (aslında, bir sayı doğrusu üzerindeki bir nokta gibi). Bir ışınlayıcı iki sayıyla, $x$ ve $y$ ile tanımlanır: $x$ konumuna getirilen gübre, anında $y$ konumuna aktarılabilir.

Çiftçi John, ışınlayıcının ilk ucunu $x = 0$ x = 0 noktasına yerleştirmeye karar vermiştir. Sizin göreviniz, diğer ucu $y$ için en iyi konumu seçmesine yardımcı olmaktır. Daha açık söylemek gerekirse, çiftliğinde $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) gübre yığını vardır. $i$ -inci yığının $a_{i}$ a_i konumundan $b_{i}$ b_i konumuna taşınması gerekmektedir ve Çiftçi John her yığını ayrı ayrı taşır. $d_{i}$ d_i, Çiftçi John'un $i$ -inci yığını taşırken gübreyle birlikte traktörüyle sürdüğü mesafeyi göstersin. Eğer $i$ -inci yığını doğrudan traktörle taşırsa, $d_{i} = ∣ a_{i} - b_{i} ∣$ d_i = |a_i - b_i| olur; eğer ışınlayıcıyı kullanırsa (örneğin, yığını traktörüyle $a_{i}$ a_i'den $x$ 'e, ardından $y$ 'den $b_{i}$ b_i'ye taşıyarak), $d_{i}$ d_i daha küçük çıkabilir.

Çiftçi John'a, ışınlayıcının diğer ucu $y$ 'yi en uygun konuma yerleştirerek elde edebileceği $d_{i}$ d_i değerlerinin toplamının mümkün olan en küçük değerini belirlemesinde yardımcı olun. Her bir yığının taşınmasında aynı $y$ konumu kullanılır.

Giriş

İlk satır $n$ tamsayısını içerir. Sonraki $n$ satırın her biri iki tamsayı içerir: $a_{i}$ a_i ve $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). Bu değerler birbirinden farklı olmak zorunda değildir.

Çıktı

Tek bir tamsayı yazdırın — Çiftçi John'un elde edebileceği $d_{i}$ d_i değerlerinin minimum toplamı. Bu sayının standart bir $32$ -bit tamsayı türüne sığmayabileceğini unutmayın, bu yüzden C/C++'ta long long gibi bir $64$ -bit tamsayı türü kullanmanız gerekebilir.

Örnekler

Bu örnekte, $y = 8$ y = 8 olarak ayarlayarak Çiftçi John $d_{1} = 2$ d_1 = 2, $d_{2} = 5$ d_2 = 5 ve $d_{3} = 3$ d_3 = 3 elde edebilir. $y$ için $[7, 10]$ aralığındaki herhangi bir değerin de optimal bir çözüm sağladığını unutmayın.

Örnek 1