Problem
आप एक प्रबंधक के रूप में काम करते हैं और अगले महीने के लिए एक कार्य योजना तैयार करते हैं। हर महीने को T समय की बराबर इकाइयों में विभाजित किया जाता है। ऐसे n कार्य हैं जिन्हें पूरा करने की आवश्यकता है। हालाँकि, आप समझते हैं कि एक महीने में सभी कार्यों को पूरा करना संभव नहीं हो सकता है और आप उनमें से कुछ को पूरा करने के लिए चुनकर एक इष्टतम योजना बनाना चाहते हैं।
प्रत्येक कार्य के लिए, हम समय ti जानते हैं जिसे इसे पूरा करने के लिए खर्च करने की आवश्यकता होती है, साथ ही लाभ pi< /sub> कि पूरा किया गया कार्य कंपनी में लाएगा। आप कुछ कार्यों की योजना बनाना चाहते हैं ताकि:
<उल>
योजना में शामिल कार्यों पर बिताया गया कुल समय T से अधिक नहीं था।
इन कार्यों से कुल लाभ अधिकतम था।
एक योजना बनाएं जिसमें ऊपर वर्णित गुण हों और इस योजना के कार्यान्वयन से होने वाले लाभ का निर्धारण करें।
कृपया ध्यान दें कि शर्तों से मेल खाने वाली एकमात्र योजना में कोई कार्य नहीं हो सकता है।
इनपुट डेटा
पहली पंक्ति में प्राकृतिक संख्याएं T (1 ≤ T ≤ 100 000) और n (1 ≤ n &le) शामिल हैं ; 10) - प्रति माह समय इकाइयों की संख्या और कार्यों की संख्या।
निम्नलिखित n पंक्तियों में दो प्राकृतिक संख्याएं हैं प्रत्येक ti और pi (1 <= ti, pi <= 100 000) - समय बिताने के लिए iवां कार्य पूरा करें और इसे पूरा करके जो लाभ प्राप्त किया जा सकता है।
छाप डेटा
एक नंबर प्रिंट करें — ऊपर लिखी शर्तों को पूरा करने वाली योजना बनाकर अधिकतम लाभ प्राप्त किया जा सकता है।
उदाहरण
<टेबल क्लास = "टेबल-एसएम टेबल-बॉर्डर टेबल-स्ट्राइप्ड टेबल-लिस्ट-टेस्ट">
<सिर>
<थ वर्ग = "अंक"> #
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |