كنوز مخبأة
Problem
ابنة ملك Flatland على وشك الزواج من الأمير تشارمينغ.
يريد الأمير أن يمنح الأميرة كنوزًا ، لكنه غير متأكد من نوع الماس الذي يختاره من مجموعته.
هناك عدد n من الماسات في مجموعة الأمير ، كل منها يتميز بالوزن w
i والقيمة v
i . & nbsp؛
يريد الأمير أن يعطي ألماسات أغلى ثمناً ، لكن الملك ذكي ولن يقبل ألماسًا يزيد وزنه الإجمالي عن R. ومن ناحية أخرى ، فإن الأمير يعتبر نفسه جشعًا لبقية حياته إذا أعطى الألماس بإجمالي وزن أقل من L.
ساعد الأمير في اختيار مجموعة من الماسات ذات أعلى قيمة إجمالية بحيث يكون الوزن الإجمالي في المقطع [L ، R].
الإدخال:
يحتوي السطر الأول على الرقم n (1 & lt؛ = n & lt؛ = 32) و L و R (0 & lt؛ = L & lt؛ = R & lt؛ = 10 18 ).
تصف الأسطر n التالية الألماس وتحتوي على رقمين لكل منهما - وزن وقيمة الماسة المقابلة (1 & lt؛ = wi، vi & lt؛ = 10 15 ).
الإخراج:
يجب أن يحتوي السطر الأول من الإخراج على k - عدد الماسات التي يجب منحها للأميرة. & nbsp؛
يجب أن يحتوي السطر الثاني على أرقام الماسات المراد إعطاؤها.
تم ترقيم الماس من 1 إلى n بالترتيب الذي يظهر به في الإدخال.
إذا كان من المستحيل تكوين هدية للأميرة ، فقم بطباعة 0 في السطر الأول من الإخراج.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
3 6 8
3 10
7 3
8 2 |
1
2 |