Farmer John doit aller en ville chercher $K$ livres de fourrage ($1 \le K \le 100$). Parcourir $D$ miles avec $K$ livres dans son camion coûte $D*K$ cents.

Le marché du comté a $N$ magasins ($1 \le N \le 100$), numérotés $1..N$, sur un segment de l’axe $X$ de longueur $E$ ($1 \le E \le 350$). Le magasin $i$, en $X_{i}$ ($0 < X_{i} < E$), peut vendre jusqu’à $F_{i}$ livres ($1 \le F_{i} \le 100$) à $C_{i}$ cents la livre ($1 \le C_{i} \le 1,000,000$). Plusieurs magasins peuvent être au même point de l’axe $X$.

FJ part de 0 et roule uniquement dans le sens positif, arrivant en $E$ avec au moins $K$ livres. Il peut s’arrêter à tout magasin sur le trajet et acheter une quantité quelconque jusqu’à son plafond.

Quel est le coût minimal pour acheter et transporter $K$ livres ? FJ sait qu’une solution existe.

Par exemple, il lui faut deux livres auprès de trois magasins en 1, 3, 4 sur la droite $0..5$ :

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

Le mieux est d’acheter une livre dans chacun des deuxième et troisième magasins, deux cents chacune, soit 4. De 3 à 4, il parcourt 1 unité avec 1 livre, coûtant $1*1 = 1$ cent.

De 4 à 5, il parcourt 1 unité avec 2 livres, coûtant $1*2 = 2$ cents.

Le total est $4+1+2 = 7$ cents.

Entrée

• Ligne 1 : trois entiers $K$, $E$, $N$ séparés par des espaces.

• Lignes $2..N+1$ : la ligne $i+1$ contient trois entiers $X_{i}$, $F_{i}$, $C_{i}$ séparés par des espaces.

Sortie

• Ligne 1 : un entier, coût minimal pour acheter et transporter le fourrage.

Exemples

Entrée 1

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

Sortie 1

7

Auteur du problème : Tom Conerly, 2009