Farmer John fährt in die Stadt, um $K$ Pfund Futter zu holen ($1 \le K \le 100$). $D$ Meilen mit $K$ Pfund auf dem Lastwagen kosten $D*K$ Cent.

Der Futtermarkt des Bezirks hat $N$ Geschäfte ($1 \le N \le 100$), nummeriert $1..N$, auf einem Abschnitt der $X$-Achse der Länge $E$ ($1 \le E \le 350$). Geschäft $i$ liegt bei $X_{i}$ ($0 < X_{i} < E$) und verkauft höchstens $F_{i}$ Pfund ($1 \le F_{i} \le 100$) zu $C_{i}$ Cent pro Pfund ($1 \le C_{i} \le 1,000,000$). An einem Punkt der $X$-Achse können mehrere Geschäfte liegen.

FJ startet bei 0 und fährt nur in positiver Richtung, bis er mit mindestens $K$ Pfund bei $E$ ankommt. Er kann unterwegs in jedem Geschäft halten und eine beliebige Menge bis zu dessen Grenze kaufen.

Wie viel kostet der Kauf und Transport von $K$ Pfund mindestens? FJ weiß, dass es eine Lösung gibt.

Zum Beispiel braucht er zwei Pfund aus drei Geschäften bei 1, 3, 4 auf der Zahlengeraden $0..5$:

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      Verfügbare Pfund Futter
          1       2   2      Cent pro Pfund

Am besten kauft er je ein Pfund im zweiten und dritten Geschäft, je zwei Cent, insgesamt 4. Von 3 nach 4 fährt er 1 Längeneinheit mit 1 Pfund, was $1*1 = 1$ Cent kostet.

Von 4 nach 5 fährt er 1 Einheit mit 2 Pfund, was $1*2 = 2$ Cent kostet.

Insgesamt sind es $4+1+2 = 7$ Cent.

Eingabe

• Zeile 1: drei durch Leerzeichen getrennte ganze Zahlen $K$, $E$, $N$.

• Zeilen $2..N+1$: Zeile $i+1$ enthält drei durch Leerzeichen getrennte ganze Zahlen $X_{i}$, $F_{i}$, $C_{i}$.

Ausgabe

• Zeile 1: eine ganze Zahl, die minimalen Kosten für Kauf und Transport des Futters.

Beispiele

Eingabe 1

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

Ausgabe 1

7

Aufgabenautor: Tom Conerly, 2009