Farmer John vai à cidade buscar $K$ libras de ração ($1 \le K \le 100$). Percorrer $D$ milhas com $K$ libras no caminhão custa $D*K$ centavos.

O mercado do condado tem $N$ lojas ($1 \le N \le 100$), numeradas $1..N$, num segmento do eixo $X$ de comprimento $E$ ($1 \le E \le 350$). A loja $i$, em $X_{i}$ ($0 < X_{i} < E$), vende até $F_{i}$ libras ($1 \le F_{i} \le 100$) a $C_{i}$ centavos por libra ($1 \le C_{i} \le 1,000,000$). Pode haver várias lojas no mesmo ponto do eixo $X$.

FJ parte de 0 e só anda no sentido positivo, chegando a $E$ com pelo menos $K$ libras. Pode parar em qualquer loja no caminho e comprar qualquer quantidade até seu limite.

Qual o custo mínimo para comprar e transportar $K$ libras? FJ sabe que existe solução.

Por exemplo, precisa de duas libras de três lojas em 1, 3, 4 na reta $0..5$:

      0   1   2   3   4   5
      +---|---+---|---|---+
          1       1   1      Libras de ração disponíveis
          1       2   2      Centavos por libra

O melhor é comprar uma libra em cada uma das lojas segunda e terceira, dois centavos cada, total 4. De 3 a 4 percorre 1 unidade com 1 libra, pagando $1*1 = 1$ centavo.

De 4 a 5 percorre 1 unidade com 2 libras, pagando $1*2 = 2$ centavos.

O total é $4+1+2 = 7$ centavos.

Entrada

• Linha 1: três inteiros $K$, $E$, $N$ separados por espaços.

• Linhas $2..N+1$: a linha $i+1$ contém três inteiros $X_{i}$, $F_{i}$, $C_{i}$ separados por espaços.

Saída

• Linha 1: um inteiro, custo mínimo para comprar e transportar a ração.

Exemplos

Entrada 1

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

Saída 1

7

Créditos do problema: Tom Conerly, 2009