Farmer John vừa đặt mua một lượng lớn kiện cỏ khô. Ông muốn sắp xếp chúng thành \(N\) đống (\(1 \leq N \leq 100\,000\)) đặt theo vòng tròn, trong đó đống \(i\) chứa \(B_i\) kiện cỏ. Không may, người lái xe tải giao cỏ đã không chú ý lắng nghe khi Farmer John cung cấp thông tin này và chỉ nhớ rằng phải để cỏ thành \(N\) đống xếp theo vòng tròn. Sau khi giao hàng, Farmer John nhận thấy đống \(i\) chứa \(A_i\) kiện cỏ. Dĩ nhiên, tổng các giá trị \(A_i\) bằng tổng các giá trị \(B_i\).

Farmer John muốn chuyển các kiện cỏ từ cách sắp xếp hiện tại (được mô tả bởi các giá trị \(A_i\)) sang cách sắp xếp đích mong muốn (được mô tả bởi các giá trị \(B_i\)). Để chuyển một kiện cỏ từ một đống sang một đống cách nó \(x\) bước quanh vòng tròn, ông phải tốn \(x\) đơn vị công sức. Hãy giúp ông tính lượng công sức ít nhất cần bỏ ra.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa hai số nguyên \(A_i\) và \(B_i\) (\(1 \leq A_i, B_i \leq 1000\)).

Dữ liệu ra

In ra lượng công sức nhỏ nhất mà Farmer John cần bỏ ra.

Ví dụ

4
7 1
3 4
9 2
1 13

13

Nguồn

USACO 2012 March Contest, Gold Division — Haybale Restacking. Tác giả đề: Brian Dean (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=128