على 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