Module: गतिशील प्रोग्रामिंग में पैटर्न

Problem

अंतर्क्षेत्रीय रोबोट प्रोग्रामिंग ओलंपियाड में, प्रतियोगिताएं एक दौर में और एक असामान्य प्रारूप में आयोजित की जाती हैं। प्रतिभागियों को कार्य क्रमिक रूप से दिए जाते हैं, सभी राउंड की शुरुआत में नहीं दिए जाते हैं, और प्रत्येक i-वें कार्य (1 ≤ i ≤ n) अपने समय पर प्रतिभागियों के लिए उपलब्ध हो जाता है_i। अगला कार्य प्राप्त होने पर, प्रत्येक प्रतिभागी को तुरंत यह निर्धारित करना चाहिए कि वह इसे हल करेगा या नहीं। यदि वह इस समस्या को हल करना चुनता है, तो उसके पास सत्यापन के लिए इसका समाधान प्रस्तुत करने के लिए t_i मिनट हैं, और इस दौरान वह दूसरी समस्या को हल करने के लिए स्विच नहीं कर सकता। यदि प्रतिभागी इस समस्या को हल करने से इंकार कर देता है, तो भविष्य में वह इसमें वापस नहीं आ सकता है। उस समय जब प्रतिभागी जिस कार्य को हल कर रहा है, उसके लिए आवंटित समय समाप्त हो गया है, वह उसी क्षण उपलब्ध होने वाले किसी अन्य कार्य को हल करना शुरू कर सकता है, यदि ऐसा कोई कार्य है, या किसी अन्य कार्य के प्रकट होने की प्रतीक्षा करें। वहीं, i-th प्रॉब्लम के सही समाधान के लिए, प्रतिभागी को c_i पॉइंट मिलते हैं।

अर्तुर, जो अंतर्क्षेत्रीय ओलंपियाड में क्षेत्रीय कृत्रिम बुद्धिमत्ता केंद्रों में से एक का प्रतिनिधित्व करता है, समझता है कि न केवल समस्याओं को हल करने की क्षमता, बल्कि यह भी सही रणनीतिक गणना है कि किन समस्याओं को हल करने की आवश्यकता है और किसे छोड़ना है, एक महत्वपूर्ण भूमिका निभाता है। ऐसा ओलंपियाड। वह, सभी प्रतिभागियों की तरह, दौरे की शुरुआत से पहले जानता है कि किस समय प्रत्येक कार्य उपलब्ध हो जाएगा, इसके समाधान के लिए कितना समय आवंटित किया जाएगा और आप इसे हल करने के लिए कितने अंक प्राप्त कर सकते हैं। आर्टूर एक प्रतिभाशाली छात्र है और इसलिए आवंटित समय में ओलंपियाड में हल करने के लिए चुने गए किसी भी समस्या को सफलतापूर्वक हल करने में सक्षम होगा और सत्यापन के लिए पास होगा।

एक प्रोग्राम लिखना आवश्यक है जो यह निर्धारित करता है कि आर्थर अधिकतम अंक प्राप्त कर सकता है जो समस्याओं के इष्टतम विकल्प के साथ-साथ ऐसी समस्याओं की संख्या और सूची के साथ प्राप्त कर सकता है।

इनपुट
पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 10⁵) ओलंपियाड में समस्याओं की संख्या है।

अगली n पंक्तियों में समस्याओं का वर्णन है, प्रत्येक पंक्ति पर तीन संख्याएँ हैं: si जिस क्षण i-th समस्या मिनटों में प्रकट होती है, t_i मिनटों में इसके समाधान के लिए आवंटित समय, और ci कितने इस समस्या को हल करने के लिए प्रतिभागी को अंक मिलेंगे (1 ≤ s_i, t_i, c_i ≤ 109< /सुप>).

छाप
पहली पंक्ति  एक ही नंबर होना चाहिए – ओलंपियाड में आर्थर को अधिकतम कितने अंक मिल सकते हैं।

दूसरी पंक्ति में एक पूर्णांक m होना चाहिए - इष्टतम विकल्प के साथ हल किए जाने वाले कार्यों की संख्या।

तीसरी पंक्ति में एम स्पेस से अलग पूर्णांक होना चाहिए - इन समस्याओं की संख्या उस क्रम में जिसमें वे हल किए गए थे। कार्य क्रमांकित हैं, एक से शुरू होकर, इनपुट फ़ाइल में वर्णित क्रम में।

यदि कई इष्टतम उत्तर हैं, तो उनमें से कोई भी प्रिंट करें।

उदाहरण

<टेबल क्लास = "टेबल-एसएम टेबल-बॉर्डर टेबल-स्ट्राइप्ड टेबल-लिस्ट-टेस्ट"> <सिर> <थ वर्ग = "अंक"> # <वें>इनपुट <वें>आउटपुट <शरीर> 1 2
1 1 1
2 2 2 3
2
1 2 2 3
1 2 1
3 2 1
2 4 3 3
1
3