Farmer John נוסע לעיר ל-$K$ ($1 \le K \le 10,000$) פאונד מספוא. מייל עם $K$ עולה $K*K$ סנטים, $D$ מייל $D*K*K$.

$N$ ($1 \le N \le 500$) חנויות $1..N$ בציר $X$ בקטע אורך $E$ ($1 \le E \le 500$) מייל. חנות $i$ ב-$X_{i}$ ($0 < X_{i} < E$), עד $F_{i}$ ($1 \le F_{i} \le 10,000$) פאונד במחיר $C_{i}$ ($1 \le C_{i} \le 10,000,000$) סנטים לפאונד. כמה חנויות יכולות באותה נקודה.

מ0 רק חיובי, מגיע $E$ עם לפחות $K$. עוצר בכל חנות וקונה כל כמות עד הגבלה.

מצאו מינימום קנייה והובלת $K$. הוא יודע שאפשר מספיק.

שני פאונד, חנויות 1,3,4 ב-$0..5$:

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

מיטבי פאונד בשנייה ובשלישית, 2 סנטים כל אחד, קנייה 4. 0–3 בלי מטען חינם; 3–4 מייל פאונד עולה $1*1*1 = 1$ סנט.

4–5 מייל שני פאונד עולה $1*2*2 = 4$ סנטים.

קנייה $2+2$, נסיעה $1+4$, סך $2 + 2 + 1 + 4 = 9$ סנטים.

קלט

• שורה 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

9

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