חברה בוחנת טכנולוגיה לייצור אנטי־חומר, המשמש כדלק בחללית בין־פלנטרית. האנטי־חומר מיוצר בעקבות ניסויים מיוחדים בכור.
ידועים $n$ סוגי ניסויים שמייצרים אנטי־חומר. בעקבות ביצוע ניסוי מסוג $i$, מתווספים למכל הפלט של הכור בין $l_i$ ל־$r_i$ גרמים של אנטי־חומר. מטעמי בטיחות אסור לצבור במכל יותר מ־$a$ גרמים של אנטי־חומר.
עלות ביצוע ניסוי מסוג $i$ היא $c_i$, ושוויו של גרם אחד של האנטי־חומר המיוצר הוא $10^9$.
אם לאחר ביצוע הניסויים נוצרו במכל $t$ גרמים של אנטי־חומר, והעלות הכוללת של ביצוע הניסויים בכור הייתה $s$, הרווח מחושב לפי הנוסחה $(t\cdot 10^9-s)$. החברה צריכה לפתח אסטרטגיה לביצוע ניסויים, שתמקסם את הרווח שאפשר להבטיח.
בהתאם לתוצאות הניסויים הקודמים, האסטרטגיה קובעת איזה סוג ניסוי לבצע, או מחליטה להפסיק את ביצוע הניסויים. אסטרטגיה מאפשרת להבטיח רווח $x$ אם לכל תוצאה אפשרית של הניסויים מתקיימים שני התנאים הבאים: ראשית, במכל הכור יהיו לכל היותר $a$ גרמים של אנטי־חומר; ושנית, הרווח יהיה לפחות $x$.
לדוגמה, נניח שאפשר לבצע רק סוג אחד של ניסוי, המייצר בין $4$ ל־$6$ גרמים של אנטי־חומר, עלות ביצועו היא $10$, וקיבולת המכל היא $17$ גרמים. אז לאחר ביצוע הניסוי פעמיים, עשויים להיות במכל בין $8$ ל־$12$ גרמים של אנטי־חומר. אם התקבלו $12$ גרמים, אסור לבצע עוד ניסוי, שכן אם יתקבלו $6$ גרמים של אנטי־חומר, המכל עלול לגלוש. בכל שאר המקרים אפשר לבצע את הניסוי בפעם השלישית ולקבל בין $12$ ל־$17$ גרמים של אנטי־חומר. במקרה הגרוע ביותר צריך לבצע את הניסוי שלוש פעמים, בעלות כוללת של $30$, והרווח יהיה $(12\cdot 10^9-30)=11\,999\,999\,970$.
עליכם לכתוב תוכנית המחשבת את הרווח המרבי $x$ שאפשר להבטיח.
קלט
השורה הראשונה של הקלט מכילה שני מספרים שלמים: $n$ — מספר סוגי הניסויים, ו־$a$ — הכמות המרבית המותרת של אנטי־חומר במכל ($1\le n\le 100$, $1\le a\le 2\,000\,000$).
כל אחת מ־$n$ השורות הבאות מכילה שלושה מספרים שלמים $l_i$, $r_i$ ו־$c_i$ — הכמות המזערית והמרבית של אנטי־חומר המתקבלת בעקבות ניסוי מסוג $i$, ועלות ניסוי מסוג זה, בהתאמה ($1\le l_i\le r_i\le a$, $1\le c_i\le 100$).
פלט
הפלט צריך להכיל מספר שלם אחד — הרווח המרבי $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 1\,000$ | לפי מקרה בדיקה | ||
| $2$ | $10$ | $1\le n\le 10$ | $1\le a\le 1\,000$ | $l_i=r_i$ | לפי מקרה בדיקה | |
| $3$ | $20$ | $1\le n\le 10$ | $1\le a\le 1\,000$ | $1,2$ | לפי מקרה בדיקה | |
| $4$ | $20$ | $1\le n\le 100$ | $1\le a\le 50\,000$ | $1\text{–}3$ | לפי מקרה בדיקה | |
| $5$ | $4$ | $1\le n\le 100$ | $1\le a\le 100\,000$ | $1\text{–}4$ | נקודות | |
| $6$ | $4$ | $1\le n\le 100$ | $1\le a\le 200\,000$ | $1\text{–}5$ | נקודות | |
| $7$ | $4$ | $1\le n\le 100$ | $1\le a\le 300\,000$ | $1\text{–}6$ | נקודות | |
| $8$ | $4$ | $1\le n\le 100$ | $1\le a\le 400\,000$ | $1\text{–}7$ | נקודות | |
| $9$ | $4$ | $1\le n\le 100$ | $1\le a\le 500\,000$ | $1\text{–}8$ | נקודות | |
| $10$ | $4$ | $1\le n\le 100$ | $1\le a\le 800\,000$ | $1\text{–}9$ | נקודות | |
| $11$ | $4$ | $1\le n\le 100$ | $1\le a\le 1\,100\,000$ | $1\text{–}10$ | נקודות | |
| $12$ | $4$ | $1\le n\le 100$ | $1\le a\le 1\,400\,000$ | $1\text{–}11$ | נקודות | |
| $13$ | $4$ | $1\le n\le 100$ | $1\le a\le 1\,700\,000$ | $1\text{–}12$ | נקודות | |
| $14$ | $4$ | $1\le n\le 100$ | $1\le a\le 2\,000\,000$ | $1\text{–}13$ | נקודות |