Lại là giao hàng


Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

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

tichpx

Comments

There are no comments at the moment.