มีอาหารทั้งหมด $N + 1$ ชนิด ได้แก่ อาหาร $N$ ชนิดที่มีหมายเลข $1, 2, \dots, N$ และเยลลี่น้ำ สำหรับ $i = 1, 2, \dots, N$ ความหวานของอาหารชนิดที่ $i$ คือ $A_i$ และความเผ็ดคือ $B_i$ ส่วนความหวานของเยลลี่น้ำคือ $0$ และความเผ็ดคือ $0$

UTPC-kun กินเยลลี่น้ำเป็นอันดับแรก จากนั้นกินอาหารชนิดที่ $1, 2, \dots, N$ ชนิดละหนึ่งครั้งพอดีในลำดับใดก็ได้ และสุดท้ายกินเยลลี่น้ำอีกครั้ง

ความสุขของ UTPC-kun มีค่าเป็น $0$ ทันทีหลังจากกินเยลลี่น้ำครั้งแรก หลังจากนั้น ทุกครั้งที่เขากินอาหาร ความสุขของเขาจะเปลี่ยนแปลงดังนี้:

• ให้ $a$ และ $b$ เป็นความหวานและความเผ็ดของอาหารที่เขากำลังกินอยู่ และให้ $a'$ และ $b'$ เป็นความหวานและความเผ็ดของอาหารที่เขากินไปก่อนหน้านี้ทันที ความสุขของเขาจะเพิ่มขึ้น $\max(a - a', b - b')$ (ค่าความสุขที่เพิ่มขึ้นสามารถติดลบได้)

จงหาความสุขสุดท้ายที่เป็นไปได้มากที่สุดของ UTPC-kun โดยการเลือกลำดับที่เหมาะสมที่สุดในการกินอาหารชนิดที่ $1, 2, \dots, N$

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะถูกกำหนดให้ในรูปแบบต่อไปนี้:

N
A_1 B_1
A_2 B_2
:
A_N B_N

• ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
• $1 \le N \le 5 \times 10^5$
• $0 \le A_i, B_i \le 10^9$

ข้อมูลส่งออก

พิมพ์คำตอบในบรรทัดเดียว

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

4
1 4
3 1
2 3
3 4

ข้อมูลส่งออกตัวอย่าง 1

6

ข้อมูลนำเข้าตัวอย่าง 2

3
1 2
2 1
1 2

ข้อมูลส่งออกตัวอย่าง 2

3

ข้อมูลนำเข้าตัวอย่าง 3

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

ข้อมูลส่งออกตัวอย่าง 3

18

หมายเหตุ

ในตัวอย่างแรก ลำดับที่เหมาะสมที่สุดลำดับหนึ่งในการกินอาหารคือ $1, 2, 3, 4$ ในกรณีนี้ ความสุขของ UTPC-kun จะเปลี่ยนแปลงดังต่อไปนี้หลังจากที่เขากินเยลลี่น้ำครั้งแรกเสร็จ:

• กินอาหารชนิดที่ $1$: ความสุขของเขาเพิ่มขึ้น $\max(1 - 0, 4 - 0) = 4$ กลายเป็น $4$
• กินอาหารชนิดที่ $2$: ความสุขของเขาเพิ่มขึ้น $\max(3 - 1, 1 - 4) = 2$ กลายเป็น $6$
• กินอาหารชนิดที่ $3$: ความสุขของเขาเพิ่มขึ้น $\max(2 - 3, 3 - 1) = 2$ กลายเป็น $8$
• กินอาหารชนิดที่ $4$: ความสุขของเขาเพิ่มขึ้น $\max(3 - 2, 4 - 3) = 1$ กลายเป็น $9$
• กินเยลลี่น้ำ: ความสุขของเขาเพิ่มขึ้น $\max(0 - 3, 0 - 4) = -3$ กลายเป็น $6$