Lại là giao hàng
Khi đại dịch Covid-19 tràn đến, cả nước áp dụng chính sách cách ly toàn xã hội, mọi người hạn chế ra ngoài. Nhiều người nhận thấy đây là cơ hội kinh doanh tốt và nhanh chóng thành lập công ty vận chuyển hàng hóa giao tận nơi cho khách hàng.
Titi là một nhân viên giao hàng cho một công ty lớn, chính sách của công ty này là cứ giao hàng mà trước một thời hạn cho trước sẽ được thưởng tùy theo món hàng mà nhân viên đó giao.
Titi nhận được \(n\) món hàng cần giao, món hàng thứ \(i\) giao không trễ quá thời gian \(t_i\) sẽ được thưởng \(v_i\) tiền. Giả sử cứ một đơn vị thời gian thì Titi giao được một món hàng, bạn hãy giúp Titi xếp thứ tự giao hàng thế nào để được nhiều tiền thưởng nhất nhé
Input
Dòng đầu số nguyên dương \(n\) là số món hàng Titi phải giao \((1 \le n \le 10^5)\)
Tiếp theo \(n\) dòng mỗi dòng chứa hai giá trị là \(t_i\) và \(v_i\) nếu món hàng này Titi giao không trễ quá \(t_i\) thì sẽ được thưởng \(v_i\) trong đó \(1 \le t_i, v_i \le 10^6\)
Output
Số tiền được thưởng cao nhất có thể nếu Titi chọn được cách giao hợp lý nhất.
Ví dụ
Input
6
3 5
3 7
1 3
2 4
2 2
4 1
Output
17
Giải thích Đề dễ giải thích ta cứ gọi đơn vị thời gian là giờ. Chúng ta có 6 món đồ chuyển cách chuyển như sau sẽ được 17 tiền:
Giờ thứ nhất chuyển món thứ tư có thời hạn trong 2 giờ nhưng giao luôn giờ thứ nhất bạn được thưởng 4 tiền
Giờ thứ hai và ba chuyển món thứ nhất và thứ hai có thời hạn trong 3 giờ bạn giao một món đúng giờ và một món sớm giờ tổng cộng 12 tiền thưởng
Giờ thứ tư tất nhiên bạn giao món thứ sáu thời hạn trong 4 giờ và bạn vẫn kịp bỏ túi 1 tiền thưởng
Comments