Deadline Killer

Xem dạng PDF

Gửi bài giải


Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Davele 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~.


Đang tải...