Đề bài
Nông trại Just Oishi Ichigo (sau đây gọi là Nông trại JOI) là một nông trại dâu tây nổi tiếng vì trải dài và hẹp theo hướng đông - tây, với lối vào nằm ở điểm cực tây của nông trại. Sau đây, vị trí cách lối vào $k$ mét về phía đông được gọi là Điểm $k$.
Bên trong Nông trại JOI có $N$ quả dâu tây đang kết trái. Chúng được đánh số từ $1$ đến $N$. Tất cả các quả dâu tây đều còn xanh cho đến thời điểm $0$. Quả dâu tây $i$ ($1 \le i \le N$) mọc tại Điểm $A_{i}$, và đến thời điểm $T_{i}$ thì chín và chuyển sang trạng thái màu đỏ.
Không thể thu hoạch dâu tây khi chúng còn xanh. Nói cách khác, quả dâu tây $i$ không thể được thu hoạch cho đến thời điểm $T_{i}$. Bạn xuất phát tại thời điểm $0$ từ lối vào nông trại ở Điểm $0$, di chuyển theo hướng đông - tây với tốc độ tối đa $1$ mét mỗi giây để thu hoạch dâu tây. Thời gian để hái một quả dâu tây có thể bỏ qua.
Cho thông tin về nông trại dâu tây, hãy viết chương trình tìm thời gian tối thiểu cần thiết để thu hoạch tất cả các quả dâu tây ở trạng thái màu đỏ rồi quay trở về lối vào.
Giới hạn
- $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$).
- Tất cả các giá trị đầu vào đều là số nguyên.
Dữ liệu vào
Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:
N A_1 T_1 A_2 T_2 : A_N T_N
Kết quả
In ra trên $1$ dòng thời gian tối thiểu cần thiết để thu hoạch tất cả các quả dâu tây ở trạng thái màu đỏ rồi quay trở về lối vào.
Ví dụ 1
Dữ liệu vào
10 1 3 2 1 3 4 4 1 5 5 6 9 7 2 8 6 9 5 10 3
Kết quả
20
Nếu bạn dành $10$ giây đầu tiên để di chuyển đến Điểm $10$, trên đường đi bạn có thể thu hoạch các quả dâu tây $2, 4, 5, 7, 8, 9, 10$ theo thứ tự này. Sau đó, nếu bạn dành $10$ giây để quay lại Điểm $0$, trên đường đi bạn có thể thu hoạch các quả dâu tây $6, 3, 1$ theo thứ tự này. Bằng cách này, tất cả $10$ quả dâu tây đều có thể được thu hoạch ở trạng thái màu đỏ.
Ví dụ 2
Dữ liệu vào
10 0 450 5 445 10 430 15 405 20 370 25 325 30 270 35 205 40 130 45 45
Kết quả
450
Bằng cách di chuyển như sau, bạn có thể thu hoạch tất cả các quả dâu tây ở trạng thái màu đỏ trong $450$ giây:
- Dành $45$ giây di chuyển đến Điểm $45$. Lúc này là thời điểm $45$ nên có thể thu hoạch quả dâu tây $10$. Sau khi thu hoạch, dành $45$ giây di chuyển về Điểm $0$.
- Sau đó, dành $40$ giây di chuyển đến Điểm $40$. Lúc này là thời điểm $130$ nên có thể thu hoạch quả dâu tây $9$. Sau khi thu hoạch, dành $40$ giây di chuyển về Điểm $0$.
- Sau đó, dành $35$ giây di chuyển đến Điểm $35$. Lúc này là thời điểm $205$ nên có thể thu hoạch quả dâu tây $8$. Sau khi thu hoạch, dành $35$ giây di chuyển về Điểm $0$.
- Sau đó, dành $30$ giây di chuyển đến Điểm $30$. Lúc này là thời điểm $270$ nên có thể thu hoạch quả dâu tây $7$. Sau khi thu hoạch, dành $30$ giây di chuyển về Điểm $0$.
- Sau đó, dành $25$ giây di chuyển đến Điểm $25$. Lúc này là thời điểm $325$ nên có thể thu hoạch quả dâu tây $6$. Sau khi thu hoạch, dành $25$ giây di chuyển về Điểm $0$.
- Sau đó, dành $20$ giây di chuyển đến Điểm $20$. Lúc này là thời điểm $370$ nên có thể thu hoạch quả dâu tây $5$. Sau khi thu hoạch, dành $20$ giây di chuyển về Điểm $0$.
- Sau đó, dành $15$ giây di chuyển đến Điểm $15$. Lúc này là thời điểm $405$ nên có thể thu hoạch quả dâu tây $4$. Sau khi thu hoạch, dành $15$ giây di chuyển về Điểm $0$.
- Sau đó, dành $10$ giây di chuyển đến Điểm $10$. Lúc này là thời điểm $430$ nên có thể thu hoạch quả dâu tây $3$. Sau khi thu hoạch, dành $10$ giây di chuyển về Điểm $0$.
- Sau đó, dành $5$ giây di chuyển đến Điểm $5$. Lúc này là thời điểm $445$ nên có thể thu hoạch quả dâu tây $2$. Sau khi thu hoạch, dành $5$ giây di chuyển về Điểm $0$.
- Bạn về đến Điểm $0$ đúng vào thời điểm $450$, nên có thể thu hoạch quả dâu tây $1$. Bạn về đến Điểm $0$ cùng lúc hoàn thành việc thu hoạch tất cả các quả dâu tây.
Ví dụ 3
Dữ liệu vào
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
Kết quả
198