El Granjero Juan necesita ir al pueblo para recoger ~K~ ~(1 \leq K \leq 100)~ libras de comida. Desplazarse ~D~ millas con ~K~ libras de comida en su camión le cuesta ~D*K~ centavos.

El estanco de alimentos del condado tiene ~N~ ~(1 \leq N \leq 100)~ tiendas (convenientemente numeradas 1..N) que venden comida. Cada tienda está ubicada en un segmento del eje X cuya longitud es ~E~ ~(1 \leq E \leq 350)~. La tienda i está en la posición ~X_i~ ~(0 < X_i < E)~ en la recta numérica y puede venderle a GJ tanto como ~F_i~ ~(1 \leq F_i \leq 100)~ libras de alimento a un costo de ~C_i~ ~(1 \leq C_i \leq 1,000,000)~ centavos por libra. Sorprendentemente, un punto dado en el eje X podría tener más de una tienda.

GJ comienza en la posición 0 de esta línea numérica y puede conducir únicamente en la dirección positiva, llegando últimamente a la posición ~E~ con al menos ~K~ libras de alimento. El puede parar en cualquiera de las tiendas de alimento a través del camino y comprar cualquier cantidad de alimento hasta el límite de la tienda.

¿Cuál es la mínima cantidad de dinero que GJ tiene que gastar para comprar y transportar las ~K~ libras de alimento? GJ sabe que siempre hay una solución.

Considere un ejemplo donde GJ necesita dos libras de alimento de tres tiendas (posiciones: 1, 3 y 4) en una línea numérica cuyo rango es 0...5:

  0   1   2   3   4   5
  +---|---+---|---|---+
      1       1   1      Cantidad disponible de alimento
      1       2   2      Centavos por libra

Lo mejor para GJ es comprar una libra de comida de tanto la segunda y la tercera tienda. El debe pagar 2 centavos para comprar cada libra de comida para un costo total de 4. Cuando GJ va de 3 a 4, él se está moviendo 1 unidad de longitud y tiene 1 libra de comida, por lo tanto él debe pagar ~1*1 = 1~ centavo.

Cuando GJ va de 4 a 5, él se está moviendo una unidad y él tiene 2 libras de alimento, por lo tanto él debe pagar ~1*2 = 2~ centavos.

Entrada

• Línea 1: Tres enteros separados por espacios: ~K, E~ y ~N~
• Líneas 2..N+1: La línea i+1 contiene tres enteros separados por espacios: ~X_i, F_i~ y ~C_i~.

Ejemplo de Entrada

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

Salida

Un solo entero que es el costo mínimo para que GJ compre y transporte el alimento.

Ejemplo de Salida

7