Farmer John va a la ciudad a comprar $K$ libras de pienso ($1 \le K \le 100$). Recorrer $D$ millas con $K$ libras en el camión cuesta $D*K$ centavos.

El mercado del condado tiene $N$ tiendas ($1 \le N \le 100$), numeradas $1..N$, en un segmento del eje $X$ de longitud $E$ ($1 \le E \le 350$). La tienda $i$, en $X_{i}$ ($0 < X_{i} < E$), vende hasta $F_{i}$ libras ($1 \le F_{i} \le 100$) a $C_{i}$ centavos por libra ($1 \le C_{i} \le 1,000,000$). Varias tiendas pueden estar en el mismo punto del eje $X$.

FJ sale de 0 y solo conduce en dirección positiva, llegando a $E$ con al menos $K$ libras. Puede parar en cualquier tienda del camino y comprar cualquier cantidad hasta su límite.

¿Cuál es el coste mínimo de comprar y transportar $K$ libras? FJ sabe que hay solución.

Por ejemplo, necesita dos libras de tres tiendas en 1, 3, 4 en la recta $0..5$:

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      Libras de pienso disponibles
          1       2   2      Centavos por libra

Lo mejor es comprar una libra en cada una de las tiendas segunda y tercera, dos centavos cada una, total 4. De 3 a 4 recorre 1 unidad con 1 libra, pagando $1*1 = 1$ centavo.

De 4 a 5 recorre 1 unidad con 2 libras, pagando $1*2 = 2$ centavos.

El total es $4+1+2 = 7$ centavos.

Entrada

• Línea 1: tres enteros $K$, $E$, $N$ separados por espacios.

• Líneas $2..N+1$: la línea $i+1$ contiene tres enteros $X_{i}$, $F_{i}$, $C_{i}$ separados por espacios.

Salida

• Línea 1: un entero, coste mínimo de comprar y transportar el pienso.

Ejemplos

Entrada 1

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

Salida 1

7

Autor del problema: Tom Conerly, 2009