โจทย์ปัญหา

ฟาร์ม Just Oishi Ichigo (ต่อไปนี้จะเรียกว่า ฟาร์ม JOI) เป็นฟาร์มสตรอว์เบอร์รีที่มีชื่อเสียงเรื่องความแคบและยาวในแนวทิศตะวันออก-ตะวันตก โดยทางเข้าจะอยู่ที่จุดตะวันตกสุดของฟาร์ม ต่อไปนี้จะเรียกสถานที่ซึ่งอยู่ห่างจากทางเข้าไปทางทิศตะวันออก $k$ เมตรว่า จุด $k$

ภายในฟาร์ม JOI มีสตรอว์เบอร์รีออกผลอยู่ $N$ ลูก แต่ละลูกมีหมายเลขตั้งแต่ $1$ ถึง $N$ กำกับไว้ สตรอว์เบอร์รีทุกลูกจะมีสีเขียวจนถึงเวลา $0$ สตรอว์เบอร์รีลูกที่ $i$ ($1 \le i \le N$) ออกผลอยู่ที่จุด $A_{i}$ และเมื่อถึงเวลา $T_{i}$ จะสุกและเปลี่ยนเป็นสถานะสีแดง

สตรอว์เบอร์รีไม่สามารถเก็บเกี่ยวได้ในขณะที่ยังเป็นสีเขียว กล่าวคือ สตรอว์เบอร์รีลูกที่ $i$ จะไม่สามารถเก็บเกี่ยวได้จนกว่าจะถึงเวลา $T_{i}$ คุณออกเดินทางในเวลา $0$ จากทางเข้าฟาร์มซึ่งอยู่ที่จุด $0$ และเคลื่อนที่ในแนวทิศตะวันออก-ตะวันตกด้วยอัตราเร็วสูงสุด $1$ เมตรต่อวินาทีพร้อมกับเก็บเกี่ยวสตรอว์เบอร์รีไปด้วย โดยสามารถละเลยเวลาที่ใช้ในการเก็บเกี่ยวสตรอว์เบอร์รีได้

เมื่อกำหนดข้อมูลเกี่ยวกับฟาร์มสตรอว์เบอร์รีมาให้ จงเขียนโปรแกรมเพื่อหาค่าต่ำสุดของเวลาที่ใช้ในการเก็บเกี่ยวสตรอว์เบอร์รีทั้งหมดในสถานะสีแดงแล้วกลับมายังทางเข้า

ข้อจำกัด

• $1 \le N \le 100\,000$
• $0 \le A_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$)
• $0 \le T_{i} \le 1\,000\,000\,000 (= 10^{9})$ ($1 \le i \le N$)
• ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม

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

ข้อมูลนำเข้าได้รับจากอินพุตมาตรฐานในรูปแบบต่อไปนี้:

N
A_1 T_1
A_2 T_2
:
A_N T_N

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

แสดงค่าต่ำสุดของเวลาที่ใช้ในการเก็บเกี่ยวสตรอว์เบอร์รีทั้งหมดในสถานะสีแดงแล้วกลับมายังทางเข้า ใน $1$ บรรทัด

ตัวอย่าง 1

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

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

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

20

หากใช้เวลา $10$ วินาทีแรกเคลื่อนที่ไปยังจุด $10$ ในระหว่างทางจะสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $2, 4, 5, 7, 8, 9, 10$ ตามลำดับนี้ได้ จากนั้นใช้เวลา $10$ วินาทีกลับมายังจุด $0$ ในระหว่างทางจะสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $6, 3, 1$ ตามลำดับนี้ได้ ด้วยวิธีนี้จะสามารถเก็บเกี่ยวสตรอว์เบอร์รีทั้ง $10$ ลูกในสถานะสีแดงได้ครบทั้งหมด

ตัวอย่าง 2

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

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

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

450

หากเคลื่อนที่ดังต่อไปนี้ จะสามารถเก็บเกี่ยวสตรอว์เบอร์รีทั้งหมดในสถานะสีแดงได้ภายใน $450$ วินาที:

1. ใช้เวลา $45$ วินาทีเคลื่อนที่ไปยังจุด $45$ ในขณะนี้เป็นเวลา $45$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $10$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $45$ วินาทีเคลื่อนที่ไปยังจุด $0$
2. หลังจากนั้น ใช้เวลา $40$ วินาทีเคลื่อนที่ไปยังจุด $40$ ในขณะนี้เป็นเวลา $130$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $9$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $40$ วินาทีเคลื่อนที่ไปยังจุด $0$
3. หลังจากนั้น ใช้เวลา $35$ วินาทีเคลื่อนที่ไปยังจุด $35$ ในขณะนี้เป็นเวลา $205$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $8$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $35$ วินาทีเคลื่อนที่ไปยังจุด $0$
4. หลังจากนั้น ใช้เวลา $30$ วินาทีเคลื่อนที่ไปยังจุด $30$ ในขณะนี้เป็นเวลา $270$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $7$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $30$ วินาทีเคลื่อนที่ไปยังจุด $0$
5. หลังจากนั้น ใช้เวลา $25$ วินาทีเคลื่อนที่ไปยังจุด $25$ ในขณะนี้เป็นเวลา $325$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $6$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $25$ วินาทีเคลื่อนที่ไปยังจุด $0$
6. หลังจากนั้น ใช้เวลา $20$ วินาทีเคลื่อนที่ไปยังจุด $20$ ในขณะนี้เป็นเวลา $370$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $5$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $20$ วินาทีเคลื่อนที่ไปยังจุด $0$
7. หลังจากนั้น ใช้เวลา $15$ วินาทีเคลื่อนที่ไปยังจุด $15$ ในขณะนี้เป็นเวลา $405$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $4$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $15$ วินาทีเคลื่อนที่ไปยังจุด $0$
8. หลังจากนั้น ใช้เวลา $10$ วินาทีเคลื่อนที่ไปยังจุด $10$ ในขณะนี้เป็นเวลา $430$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $3$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $10$ วินาทีเคลื่อนที่ไปยังจุด $0$
9. หลังจากนั้น ใช้เวลา $5$ วินาทีเคลื่อนที่ไปยังจุด $5$ ในขณะนี้เป็นเวลา $445$ จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $2$ ได้ หลังเก็บเกี่ยวแล้วใช้เวลา $5$ วินาทีเคลื่อนที่ไปยังจุด $0$
10. ไปถึงจุด $0$ ในเวลา $450$ พอดี จึงสามารถเก็บเกี่ยวสตรอว์เบอร์รีลูกที่ $1$ ได้ และมาถึงจุด $0$ พร้อมกับที่เก็บเกี่ยวสตรอว์เบอร์รีครบทั้งหมดพอดี

ตัวอย่าง 3

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

15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33

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

198