يذهب 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      السنتات للرطل

الأفضل رطل من الثاني والثالث، سنتان لكل رطل، شراء 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