Farmer John va en ville chercher $K$ ($1 \le K \le 10,000$) livres de fourrage. Un mile avec $K$ coûte $K*K$ cents, $D$ miles $D*K*K$.

$N$ ($1 \le N \le 500$) magasins $1..N$ sur l'axe $X$, segment de $E$ ($1 \le E \le 500$) miles. Magasin $i$ en $X_{i}$ ($0 < X_{i} < E$), jusqu'à $F_{i}$ ($1 \le F_{i} \le 10,000$) livres à $C_{i}$ ($1 \le C_{i} \le 10,000,000$) cents par livre. Plusieurs peuvent partager un point.

De 0 uniquement vers le positif, arrive à $E$ avec au moins $K$. Arrêt possible partout, achat quelconque jusqu'au plafond du magasin.

Trouvez le minimum achat et transport de $K$ livres. Il peut en acheter assez.

Deux livres requises, trois magasins en 1,3,4 sur $0..5$ :

      0   1   2   3   4   5  X
      +---|---+---|---|---+
          1       1   1      Livres disponibles
          1       2   2      Cents par livre

Optimalement une livre au deuxième et troisième, 2 cents chacune, achat 4. 0–3 sans charge gratuit ; 3–4 un mile une livre coûte $1*1*1 = 1$ cent.

4–5 un mile deux livres coûte $1*2*2 = 4$ cents.

Fourrage $2+2$, trajet $1+4$, total $2 + 2 + 1 + 4 = 9$ cents.

Entrée

• Ligne 1 : entiers $K$, $E$, $N$ séparés par des espaces.
• Lignes $2..N+1$ : ligne $i+1$, entiers $X_{i}$, $F_{i}$, $C_{i}$ séparés par des espaces.

Sortie

• Ligne 1 : entier, minimum achat et transport.

Exemples

Entrée 1

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

Sortie 1

9

Auteur du problème : Tom Conerly, 2009