تختبر شركة تقنية لإنتاج المادة المضادة، التي تُستخدم وقودًا في مركبة فضائية بين الكواكب. تُنتَج المادة المضادة نتيجة تجارب خاصة في مفاعل.
هناك $n$ أنواع معروفة من التجارب التي تنتج المادة المضادة. تضيف تجربة من النوع $i$ إلى حاوية الخرج في المفاعل ما بين $l_i$ و$r_i$ غرامًا من المادة المضادة. ولأسباب تتعلق بالسلامة، يُمنع تراكم أكثر من $a$ غرامًا من المادة المضادة في الحاوية.
تكلفة إجراء تجربة من النوع $i$ هي $c_i$، وقيمة غرام واحد من المادة المضادة المنتَجة هي $10^9$.
إذا أصبح في الحاوية بعد إجراء التجارب $t$ غرامًا من المادة المضادة، وكانت التكلفة الإجمالية لإجراء التجارب في المفاعل $s$، فإن الربح يُحدَّد بالصيغة $(t\cdot10^9-s)$. تحتاج الشركة إلى وضع استراتيجية لإجراء التجارب تزيد إلى أقصى حد الربح الذي يمكن ضمان الحصول عليه.
تحدد الاستراتيجية، حسب نتائج التجارب السابقة، نوع التجربة التي يجب إجراؤها، أو تقرر إيقاف إجراء المزيد من التجارب. تضمن الاستراتيجية ربحًا قدره $x$ إذا تحقق، مهما كانت نتائج التجارب، أولًا أن حاوية المفاعل تحتوي على ما لا يزيد عن $a$ غرامًا من المادة المضادة، وثانيًا أن الربح لا يقل عن $x$.
على سبيل المثال، لنفترض أن هناك نوعًا واحدًا فقط من التجارب، ينتج ما بين $4$ و$6$ غرامات من المادة المضادة، وتكلفة إجرائه $10$، وسعة الحاوية $17$ غرامًا. بعد إجراء التجربة مرتين، قد تحتوي الحاوية على ما بين $8$ و$12$ غرامًا من المادة المضادة. إذا نتج $12$ غرامًا، فلا يجوز إجراء التجربة مرة أخرى، لأن إنتاج $6$ غرامات قد يؤدي إلى تجاوز سعة الحاوية. في الحالات الأخرى، يمكن إجراء التجربة مرة ثالثة والحصول على ما بين $12$ و$17$ غرامًا من المادة المضادة. في أسوأ الحالات، يجب إجراء التجربة ثلاث مرات بتكلفة إجمالية $30$، ويكون الربح $(12\cdot10^9-30)=11\,999\,999\,970$.
اكتب برنامجًا يحدد أكبر ربح $x$ يمكن ضمان الحصول عليه.
الإدخال
يحتوي السطر الأول من الإدخال على عددين صحيحين: $n$، عدد أنواع التجارب، و$a$، أكبر كمية مسموح بها من المادة المضادة في الحاوية ($1\le n\le100$، $1\le a\le2\,000\,000$).
يحتوي كل سطر من الأسطر $n$ التالية على ثلاثة أعداد صحيحة $l_i$ و$r_i$ و$c_i$، وهي على الترتيب أقل وأكبر كمية من المادة المضادة الناتجة عن تجربة من النوع $i$، وتكلفة إجراء تجربة من هذا النوع ($1\le l_i\le r_i\le a$، $1\le c_i\le100$).
الإخراج
يجب أن يحتوي الإخراج على عدد صحيح واحد، وهو أكبر ربح $x$ يمكن ضمان الحصول عليه.
أمثلة
الإدخال 1
1 17 4 6 10
الإخراج 1
11999999970
الإدخال 2
2 11 2 2 100 3 5 5
الإخراج 2
9999999890
المهام الفرعية
| المهمة الفرعية | النقاط | القيود على $n$ | القيود على $a$ | قيود إضافية | المهام الفرعية المطلوبة | النتائج أثناء المسابقة |
|---|---|---|---|---|---|---|
| 1 | 10 | $n=1$ | $1\le a\le 1000$ | لكل اختبار | ||
| 2 | 10 | $1\le n\le 10$ | $1\le a\le 1000$ | $l_i=r_i$ | لكل اختبار | |
| 3 | 20 | $1\le n\le 10$ | $1\le a\le 1000$ | 1, 2 | لكل اختبار | |
| 4 | 20 | $1\le n\le 100$ | $1\le a\le 50000$ | 1–3 | لكل اختبار | |
| 5 | 4 | $1\le n\le 100$ | $1\le a\le 100000$ | 1–4 | النقاط | |
| 6 | 4 | $1\le n\le 100$ | $1\le a\le 200000$ | 1–5 | النقاط | |
| 7 | 4 | $1\le n\le 100$ | $1\le a\le 300000$ | 1–6 | النقاط | |
| 8 | 4 | $1\le n\le 100$ | $1\le a\le 400000$ | 1–7 | النقاط | |
| 9 | 4 | $1\le n\le 100$ | $1\le a\le 500000$ | 1–8 | النقاط | |
| 10 | 4 | $1\le n\le 100$ | $1\le a\le 800000$ | 1–9 | النقاط | |
| 11 | 4 | $1\le n\le 100$ | $1\le a\le 1100000$ | 1–10 | النقاط | |
| 12 | 4 | $1\le n\le 100$ | $1\le a\le 1400000$ | 1–11 | النقاط | |
| 13 | 4 | $1\le n\le 100$ | $1\le a\le 1700000$ | 1–12 | النقاط | |
| 14 | 4 | $1\le n\le 100$ | $1\le a\le 2000000$ | 1–13 | النقاط |