Bạn có $n$ tấm thẻ bài trên tay, yêu cầu điền chúng vào các ô trống sao cho kết quả tính toán là nhỏ nhất.

Mỗi tấm thẻ có hai mặt, in hai con số khác nhau; số 6 không được dùng như số 9, số 9 cũng không được dùng như số 6.

Giữa các ô là các dấu - và + xếp xen kẽ, quy tắc định dạng:

• Khi $n=8$, định dạng là: $-O+O-O+O-O+O-O+O$
• Quy tắc tổng quát: dấu đầu tiên là dấu trừ, các dấu +, - phía sau xuất hiện xen kẽ, tổng cộng có $n$ vị trí cần điền.

Khi điền thẻ bài, có thể đổi chỗ các tấm thẻ tùy ý, chọn mặt trước hoặc mặt sau của thẻ tùy ý.

Dữ liệu vào

Dòng đầu tiên là một số nguyên dương $n$.

Tiếp theo là $n$ dòng, mỗi dòng hai số nguyên $A_i$ và $B_i$, lần lượt biểu thị số ở mặt trước và mặt sau của tấm thẻ thứ $i$.

Dữ liệu ra

In ra một dòng chứa một số nguyên, biểu thị kết quả tính toán nhỏ nhất có thể đạt được.

Ví dụ

Input

6
-8 12
0 5
7 -3
10 -7
-2 7
1 4

Output

-34

Ghi chú

Phạm vi dữ liệu

• $n \le 5 \times 10^5$
• $|A_i|,|B_i| \le 10^7$