Tối đa tổng thưởng hoàn thành sớm

Bối cảnh và bài toán

Có n công việc, công việc i mất a[i] thời gian và có mốc d[i]. Khi hoàn thành ở thời điểm f[i], điểm nhận được là d[i]-f[i]. Phải làm tất cả công việc tuần tự, không nghỉ giữa chừng.

Yêu cầu

Tìm tổng điểm lớn nhất có thể đạt.

Input

• Dòng 1: n.
• n dòng: a d.

Output

In tổng điểm lớn nhất.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= a, d <= 10^6

Chấm điểm

Ví dụ 1

Input

3
6 10
8 15
5 12

Output

2

Giải thích. Thứ tự tối ưu theo thời lượng tăng: 5,6,8; tổng reward bằng 2.

Ví dụ 2

Input

1
5 3

Output

-2

Giải thích. Hoàn thành ở thời điểm 5 nên reward = 3-5.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Tasks and Deadlines (Task 1630).

Tham khảo: https://www.cses.fi/problemset/task/1630/