Deadline Killer
Xem dạng PDFDavele có ~N~ công việc. Công việc ~i~ cần ~S_i~ đơn vị thời gian và không được thực hiện trước thời điểm ~T_i~. Có thể tạm dừng rồi tiếp tục công việc, tuy nhiên tại mỗi thời điểm chỉ được thực hiện nhiều nhất một công việc. Gọi ~C_i~ là thời điểm hoàn thành công việc ~i~. Hãy tìm giá trị nhỏ nhất của ~\sum_{i=1}^{N} C_i~.
Input
Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 2 \cdot 10^5~).
Mỗi dòng trong ~N~ dòng tiếp theo chứa hai số nguyên ~T_i~ và ~S_i~ (~0 \le T_i \le 10^9~, ~1 \le S_i \le 10^6~).
Output
Một dòng chứa giá trị nhỏ nhất của ~\sum_{i=1}^{N} C_i~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10~ | ~N \le 2~ |
| 2 | ~20~ | ~T_1 = T_2 = \cdots = T_N~ |
| 3 | ~20~ | ~S_1 = S_2 = \cdots = S_N~ |
| 4 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
2
0 10
5 3
Sample Output 1
21
Notes
Làm công việc ~1~ từ thời điểm ~0~ đến thời điểm ~5~. Công việc ~2~ bắt đầu ở thời điểm ~5~ và xong ở thời điểm ~8~. Sau đó công việc ~1~ làm tiếp và xong ở thời điểm ~13~. Tổng là ~8 + 13 = 21~.