Một trong những công việc đồng áng mà bác nông dân John ghét nhất là vận chuyển những lượng lớn phân bò. Để đơn giản hóa quá trình này, ông nghĩ ra một phát minh xuất sắc: máy dịch chuyển phân bò! Thay vì chở phân giữa hai điểm bằng chiếc xe kéo phía sau máy kéo, ông có thể dùng máy dịch chuyển phân để đưa phân tức thời từ vị trí này sang vị trí khác.

Trang trại của bác nông dân John nằm dọc theo một con đường thẳng rất dài, nên mỗi vị trí trong trang trại có thể được mô tả đơn giản bằng vị trí của nó trên con đường này (tương ứng với một điểm trên trục số). Một máy dịch chuyển được mô tả bởi hai số \(x\) và \(y\): phân được đưa đến vị trí \(x\) có thể được dịch chuyển tức thời đến vị trí \(y\).

Bác nông dân John quyết định xây một máy dịch chuyển có đầu thứ nhất đặt tại \(x=0\); nhiệm vụ của bạn là giúp ông xác định cách chọn tốt nhất cho đầu còn lại \(y\). Cụ thể, có \(N\) đống phân trong trang trại của ông (\(1 \leq N \leq 100{,}000\)). Đống thứ \(i\) cần được chuyển từ vị trí \(a_i\) đến vị trí \(b_i\), và bác nông dân John vận chuyển từng đống riêng biệt với các đống khác. Gọi \(d_i\) là quãng đường bác nông dân John lái máy kéo trong lúc chở đống phân thứ \(i\). Khi ông chở trực tiếp đống phân thứ \(i\) bằng máy kéo, ta có thể có \(d_i = |a_i-b_i|\); hoặc \(d_i\) có thể nhỏ hơn nếu ông dùng máy dịch chuyển (chẳng hạn bằng cách dùng máy kéo chở phân từ \(a_i\) đến \(x\), rồi từ \(y\) đến \(b_i\)).

Hãy giúp bác nông dân John xác định giá trị nhỏ nhất có thể của tổng các \(d_i\) bằng cách chọn cẩn thận một vị trí tối ưu để xây đầu còn lại \(y\) của máy dịch chuyển. Cùng một vị trí \(y\) được sử dụng khi vận chuyển mọi đống phân.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(a_i\) và \(b_i\), mỗi số là một số nguyên trong khoảng \(-10^8 \ldots 10^8\). Các giá trị này không nhất thiết đôi một khác nhau.

Dữ liệu ra

In ra một số duy nhất là tổng nhỏ nhất của các \(d_i\) mà bác nông dân John có thể đạt được. Lưu ý rằng số này có thể quá lớn để lưu trong một số nguyên \(32\) bit tiêu chuẩn, vì vậy bạn có thể cần dùng kiểu số nguyên lớn như long long trong C/C++. Ngoài ra, bạn cũng nên cân nhắc xem đáp án có nhất thiết là một số nguyên hay không...

Ví dụ

3
-5 -7
-3 10
-2 7

10

Nguồn

USACO 2018 February Contest, Silver — Teleportation

Tác giả bài toán: Brian Dean.