Farmer John va in città per $K$ ($1 \le K \le 10,000$) libbre. Miglio con $K$ costa $K*K$ centesimi, $D$ miglia $D*K*K$.

$N$ ($1 \le N \le 500$) negozi $1..N$ sull'asse $X$, segmento lungo $E$ ($1 \le E \le 500$) miglia. Negozio $i$ in $X_{i}$ ($0 < X_{i} < E$), fino $F_{i}$ ($1 \le F_{i} \le 10,000$) libbre a $C_{i}$ ($1 \le C_{i} \le 10,000,000$) centesimi ciascuna. Più negozi possono coincidere.

Da 0 solo positivo, arriva a $E$ con almeno $K$. Ferma qualsiasi negozio e compra quantità qualsiasi entro limite.

Trova minimo acquisto e trasporto di $K$. Può comprarne abbastanza.

Due libbre, negozi 1,3,4 nel tratto $0..5$:

      0   1   2   3   4   5  X
      +---|---+---|---|---+
          1       1   1      Libbre disponibili
          1       2   2      Centesimi per libbra

Meglio una libbra al secondo e terzo, 2 centesimi ciascuna, acquisto 4. 0–3 senza carico gratis; 3–4 un miglio una libbra costa $1*1*1 = 1$.

4–5 un miglio due libbre costa $1*2*2 = 4$ centesimi.

Acquisto $2+2$, viaggio $1+4$, totale $2 + 2 + 1 + 4 = 9$ centesimi.

Input

• Riga 1: interi $K$, $E$, $N$ con spazi.
• Righe $2..N+1$: riga $i+1$, interi $X_{i}$, $F_{i}$, $C_{i}$ con spazi.

Output

• Riga 1: intero, minimo acquisto e trasporto.

Esempi

Input 1

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

Output 1

9

Autore del problema: Tom Conerly, 2009