Farmer John va al pueblo por $K$ ($1 \le K \le 10,000$) libras. Milla con $K$ cuesta $K*K$ centavos, $D$ millas $D*K*K$.

$N$ ($1 \le N \le 500$) tiendas $1..N$ en eje $X$, tramo de $E$ ($1 \le E \le 500$) millas. Tienda $i$ en $X_{i}$ ($0 < X_{i} < E$), hasta $F_{i}$ ($1 \le F_{i} \le 10,000$) libras a $C_{i}$ ($1 \le C_{i} \le 10,000,000$) centavos cada una. Puede haber varias por punto.

De 0 solo en dirección positiva, llega a $E$ con al menos $K$. Para en cualquier tienda, compra cualquier cantidad hasta límite.

Halla mínimo de compra y transporte de $K$ libras. Hay suficiente.

Dos libras, tres tiendas en 1,3,4 del tramo $0..5$:

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

Óptimo una libra en segunda y tercera, 2 centavos cada una, compra 4. 0–3 sin carga gratis; 3–4 una milla con una libra cuesta $1*1*1 = 1$.

4–5 una milla con dos cuesta $1*2*2 = 4$ centavos.

Compra $2+2$, viaje $1+4$, total $2 + 2 + 1 + 4 = 9$ centavos.

Entrada

• Línea 1: enteros $K$, $E$, $N$ con espacios.
• Líneas $2..N+1$: línea $i+1$, enteros $X_{i}$, $F_{i}$, $C_{i}$ con espacios.

Salida

• Línea 1: entero, mínimo compra y transporte.

Ejemplos

Entrada 1

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

Salida 1

9

Autor del problema: Tom Conerly, 2009