Farmer John vai à cidade buscar $K$ ($1 \le K \le 10,000$) libras. Milha com $K$ custa $K*K$ centavos, $D$ milhas $D*K*K$.

$N$ ($1 \le N \le 500$) lojas $1..N$ no eixo $X$, trecho de $E$ ($1 \le E \le 500$) milhas. Loja $i$ em $X_{i}$ ($0 < X_{i} < E$), até $F_{i}$ ($1 \le F_{i} \le 10,000$) libras a $C_{i}$ ($1 \le C_{i} \le 10,000,000$) centavos cada. Várias lojas podem estar no mesmo ponto.

De 0 só sentido positivo, chega a $E$ com pelo menos $K$. Pode parar em qualquer loja, comprar quantidade qualquer até limite.

Ache mínimo de compra e transporte de $K$ libras. Há suficiente.

Duas libras, três lojas em 1,3,4 no trecho $0..5$:

      0   1   2   3   4   5  X
      +---|---+---|---|---+
          1       1   1      Libras disponíveis
          1       2   2      Centavos por libra

Melhor uma libra na segunda e terceira, 2 centavos cada, compra 4. 0–3 sem carga grátis; 3–4 uma milha com uma libra custa $1*1*1 = 1$.

4–5 uma milha com duas custa $1*2*2 = 4$ centavos.

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

Entrada

• Linha 1: inteiros $K$, $E$, $N$ com espaços.
• Linhas $2..N+1$: linha $i+1$, inteiros $X_{i}$, $F_{i}$, $C_{i}$ com espaços.

Saída

• Linha 1: inteiro, mínimo compra e transporte.

Exemplos

Entrada 1

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

Saída 1

9

Autor do problema: Tom Conerly, 2009