Farmer John fährt für $K$ ($1 \le K \le 10,000$) Pfund Futter zur Stadt. Meile mit $K$ kostet $K*K$ Cent, $D$ Meilen $D*K*K$.

$N$ ($1 \le N \le 500$) Läden $1..N$ auf $X$-Achse, Länge $E$ ($1 \le E \le 500$) Meilen. Laden $i$ bei $X_{i}$ ($0 < X_{i} < E$), bis $F_{i}$ ($1 \le F_{i} \le 10,000$) Pfund je $C_{i}$ ($1 \le C_{i} \le 10,000,000$) Cent. Mehrere Läden an einem Ort möglich.

Ab 0 nur positiv, Ankunft $E$ mit mindestens $K$. Stoppt beliebige Läden, kauft beliebige Menge bis deren Grenze.

Finde minimale Kauf- und Transportkosten für $K$. Genug Kaufmenge ist garantiert.

Zwei Pfund, Läden bei 1,3,4 im Abschnitt $0..5$:

      0   1   2   3   4   5  X
      +---|---+---|---|---+
          1       1   1      Verfügbare Pfund
          1       2   2      Cent je Pfund

Am günstigsten je ein Pfund im zweiten und dritten, je 2 Cent, Kauf 4. 0–3 ohne Futter kostenlos; 3–4 eine Meile ein Pfund kostet $1*1*1 = 1$ Cent.

4–5 eine Meile zwei Pfund kostet $1*2*2 = 4$ Cent.

Kauf $2+2$, Fahrt $1+4$, insgesamt $2 + 2 + 1 + 4 = 9$ Cent.

Eingabe

• Zeile 1: ganze $K$, $E$, $N$ mit Leerzeichen.
• Zeilen $2..N+1$: Zeile $i+1$, ganze $X_{i}$, $F_{i}$, $C_{i}$ mit Leerzeichen.

Ausgabe

• Zeile 1: Ganzzahl, minimale Kauf- und Transportkosten.

Beispiele

Eingabe 1

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

Ausgabe 1

9

Aufgabenautor: Tom Conerly, 2009