Có tổng cộng $N + 1$ loại thức ăn: $N$ loại thức ăn được đánh số $1, 2, \dots, N$, và thạch nước. Với $i = 1, 2, \dots, N$, độ ngọt của thức ăn $i$ là $A_i$ và độ cay của nó là $B_i$. Độ ngọt của thạch nước là $0$ và độ cay của nó là $0$.

UTPC-kun đầu tiên ăn thạch nước, sau đó ăn các thức ăn $1, 2, \dots, N$ mỗi loại đúng một lần theo thứ tự bất kỳ, và cuối cùng lại ăn thạch nước một lần nữa.

Độ hạnh phúc của UTPC-kun bằng $0$ ngay sau khi ăn miếng thạch nước đầu tiên. Sau đó, mỗi khi cậu ăn một loại thức ăn, độ hạnh phúc của cậu thay đổi như sau:

• Gọi $a$ và $b$ lần lượt là độ ngọt và độ cay của thức ăn cậu đang ăn, đồng thời gọi $a'$ và $b'$ lần lượt là độ ngọt và độ cay của thức ăn cậu vừa ăn ngay trước đó. Độ hạnh phúc của cậu tăng thêm $\max(a - a', b - b')$. (Lượng tăng của độ hạnh phúc có thể là số âm.)

Hãy tìm độ hạnh phúc cuối cùng lớn nhất có thể của UTPC-kun bằng cách chọn thứ tự tối ưu để ăn các thức ăn $1, 2, \dots, N$.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• Tất cả các giá trị đầu vào đều là số nguyên.
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

Kết quả

In câu trả lời trên một dòng duy nhất.

Ví dụ

Ví dụ đầu vào 1

4
1 4
3 1
2 3
3 4

Ví dụ đầu ra 1

6

Ví dụ đầu vào 2

3
1 2
2 1
1 2

Ví dụ đầu ra 2

3

Ví dụ đầu vào 3

6
3 1
4 1
5 9
2 6
5 3
5 8

Ví dụ đầu ra 3

18

Ghi chú

Ở ví dụ thứ nhất, một thứ tự tối ưu để ăn các thức ăn là $1, 2, 3, 4$. Trong trường hợp này, độ hạnh phúc của UTPC-kun thay đổi như sau sau khi cậu ăn xong miếng thạch nước đầu tiên:

• Ăn thức ăn $1$: Độ hạnh phúc tăng thêm $\max(1 - 0, 4 - 0) = 4$, trở thành $4$.
• Ăn thức ăn $2$: Độ hạnh phúc tăng thêm $\max(3 - 1, 1 - 4) = 2$, trở thành $6$.
• Ăn thức ăn $3$: Độ hạnh phúc tăng thêm $\max(2 - 3, 3 - 1) = 2$, trở thành $8$.
• Ăn thức ăn $4$: Độ hạnh phúc tăng thêm $\max(3 - 2, 4 - 3) = 1$, trở thành $9$.
• Ăn thạch nước: Độ hạnh phúc tăng thêm $\max(0 - 3, 0 - 4) = -3$, trở thành $6$.