कार्य और डेडलाइन्स
n कार्य दिए गए हैं, जिनकी अपनी-अपनी डेडलाइन और समय से पहले पूरा करने पर मिलने वाला मुनाफ़ा तय है। आपको पता लगाना है कि अधिकतम कुल मुनाफ़ा कितना हो सकता है। हर कार्य को पूरा करने में 1 दिन लगता है। यदि आप किसी कार्य को उसकी डेडलाइन से पहले पूरा नहीं करते हैं, तो आपको कुछ भी प्राप्त नहीं होगा।आप दिन 1 से शुरू करते हैं। ऐसे में आप कितना मुनाफ़ा कमा सकते हैं?
इनपुट
इनपुट की पहली पंक्ति में एक पूर्णांक
n (1 ≤ n ≤ ) होता है जो कार्यों की संख्या दर्शाता है।अगली
n पंक्तियों में प्रत्येक कार्य की डेडलाइन और मुनाफ़ा दर्शाने वाले दो पूर्णांक (1 ≤ , ≤ ) स्पेस से अलग-अलग लिखे होते हैं।आउटपुट
कार्यक्रम को वह अधिकतम कुल मुनाफ़ा दिखाना चाहिए जो आप कमा सकते हैं।
उदाहरण
इनपुट | आउटपुट |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
स्पष्टीकरण
- 10 + 3 + 7
- पहले, डेडलाइन 1 वाले कार्य को पूरा करें ⇒ 3 कमाएँ
- फिर, डेडलाइन 2 वाले कार्य को पूरा करें ⇒ 7 कमाएँ
- उसके बाद, डेडलाइन 4 वाले कार्य को पूरा करें ⇒ 10 कमाएँ
- 100 + 200 + 300 + 200 (सिर्फ डेडलाइन 4 वाले कार्य करें)
- पहले, 100 मुनाफ़े वाले कार्य को पूरा करें
- फिर, 200 मुनाफ़े वाले कार्य को पूरा करे
- इसके बाद, 300 मुनाफ़े वाले कार्य को पूरा करें
- अंत में, 200 मुनाफ़े वाले कार्य को पूरा करें
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB