Farmer John נוסע לעיירה לקנות $K$ פאונד מספוא ($1 \le K \le 100$). נסיעה של $D$ מייל עם $K$ פאונד במשאית עולה $D*K$ סנט.

בשוק המחוז $N$ חנויות ($1 \le N \le 100$), ממוספרות $1..N$, על קטע מציר $X$ שאורכו $E$ ($1 \le E \le 350$). חנות $i$ נמצאת ב־$X_{i}$ ($0 < X_{i} < E$), מוכרת עד $F_{i}$ פאונד ($1 \le F_{i} \le 100$) במחיר $C_{i}$ סנט לפאונד ($1 \le C_{i} \le 1,000,000$). כמה חנויות עשויות להיות באותה נקודה בציר $X$.

FJ מתחיל ב־0 ונוסע רק בכיוון החיובי, ולבסוף מגיע ל־$E$ עם לפחות $K$ פאונד. הוא יכול לעצור בכל חנות בדרך ולקנות כל כמות עד למגבלת החנות.

מה העלות המזערית לקניית והובלת $K$ פאונד? FJ יודע שיש פתרון.

למשל דרושים שני פאונד משלוש חנויות במיקומים 1, 3, 4 על הישר $0..5$:

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      פאונד מספוא זמינים
          1       2   2      סנט לפאונד

עדיף לקנות פאונד בכל אחת מהחנויות השנייה והשלישית, שני סנט לכל אחד, סך 4. מ־3 ל־4 הוא נוסע יחידת אורך אחת עם פאונד אחד, בעלות $1*1 = 1$ סנט.

מ־4 ל־5 הוא נוסע יחידה אחת עם שני פאונד, בעלות $1*2 = 2$ סנט.

העלות הכוללת $4+1+2 = 7$ סנט.

קלט

• שורה 1: שלושה שלמים $K$, $E$, $N$ מופרדים ברווחים.

• שורות $2..N+1$: שורה $i+1$ מכילה שלושה שלמים $X_{i}$, $F_{i}$, $C_{i}$ מופרדים ברווחים.

פלט

• שורה 1: שלם אחד, העלות המזערית לקנייה ולהובלה של המספוא.

דוגמאות

קלט 1

2 5 3
3 1 2
4 1 2
1 1 1

פלט 1

7

מחבר הבעיה: Tom Conerly, 2009