Farmer John va in città a prendere $K$ libbre di mangime ($1 \le K \le 100$). Percorrere $D$ miglia con $K$ libbre nel camion costa $D*K$ centesimi.

Il mercato della contea ha $N$ negozi ($1 \le N \le 100$), numerati $1..N$, su un segmento dell’asse $X$ lungo $E$ ($1 \le E \le 350$). Il negozio $i$, in $X_{i}$ ($0 < X_{i} < E$), vende fino a $F_{i}$ libbre ($1 \le F_{i} \le 100$) a $C_{i}$ centesimi per libbra ($1 \le C_{i} \le 1,000,000$). Più negozi possono trovarsi nello stesso punto dell’asse $X$.

FJ parte da 0 e procede solo nel verso positivo, arrivando a $E$ con almeno $K$ libbre. Può fermarsi in qualsiasi negozio lungo il percorso e comprare qualsiasi quantità entro il limite del negozio.

Qual è il costo minimo di acquisto e trasporto di $K$ libbre? FJ sa che esiste una soluzione.

Per esempio, servono due libbre da tre negozi in 1, 3, 4 sulla retta $0..5$:

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

Conviene comprare una libbra in ciascuno del secondo e terzo negozio, due centesimi ciascuna, totale 4. Da 3 a 4 percorre 1 unità con 1 libbra, pagando $1*1 = 1$ centesimo.

Da 4 a 5 percorre 1 unità con 2 libbre, pagando $1*2 = 2$ centesimi.

Il totale è $4+1+2 = 7$ centesimi.

Input

• Riga 1: tre interi $K$, $E$, $N$ separati da spazi.

• Righe $2..N+1$: la riga $i+1$ contiene tre interi $X_{i}$, $F_{i}$, $C_{i}$ separati da spazi.

Output

• Riga 1: un intero, il costo minimo per comprare e trasportare il mangime.

Esempi

Input 1

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

Output 1

7

Autore del problema: Tom Conerly, 2009