Farmer John đặt nhiều kiện cỏ, muốn $N$ đống theo vòng tròn ($1 \le N \le 100,000$), đống $i$ có $B_{i}$ kiện. Tài xế không nghe kỹ, chỉ nhớ $N$ đống theo vòng tròn. Sau giao, đống $i$ có $A_{i}$ kiện. Tổng $A_{i}$ và $B_{i}$ dĩ nhiên bằng nhau.

Ông muốn chuyển bố trí hiện tại $A_{i}$ thành đích $B_{i}$. Chuyển một kiện tới đống cách $x$ bước quanh vòng cần $x$ đơn vị công. Tìm công ít nhất.

Dữ liệu vào

• Dòng $1$: số nguyên $N$.

• Các dòng $2..1+N$: dòng $i+1$ chứa $A_{i}$ và $B_{i}$ ($1 \le A_{i}, B_{i} \le 1000$).

Dữ liệu ra

Ví dụ

Dữ liệu vào 1

4
7 1
3 4
9 2
1 13

Dữ liệu ra 1

13

Ghi chú

Có $4$ đống gồm $7$, $3$, $9$, $1$ kiện; đích là $1$, $4$, $2$, $13$.

Ít nhất $13$ đơn vị công: chuyển $6$ kiện từ đống $1$ tới $4$, $1$ từ $3$ tới $2$, $6$ từ $3$ tới $4$.

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