Description

John drives to town and wants to bring back $K$ tons of feed. Transporting feed costs money: if his car currently carries $X$ tons, the cost per kilometer is $X^2$ yuan, so driving $D$ kilometers costs $D\times X^2$ yuan. John can buy feed from $N$ stores, all located on a number line. Store $i$ is at position $X_i$, sells feed at $C_i$ yuan per ton, and has $F_i$ tons in stock.

John starts at $X=0$ and travels in the positive direction along the axis. His home is at $X=E$. What is the minimum total cost for John to bring $K$ tons of feed home? Assume the sum of all stores’ stocks is at least $K$.

For example, suppose there are three stores as shown below:

If $K=2$, John’s optimal choice is to buy from the two stores closer to home. The money spent on the road is $1+4=5$, the money spent at the stores is $2+2=4$, for a total of $9$ yuan.

Input Format

The first line contains three integers $K$, $E$, $N$.

Lines $2$ to $N+1$: line $i+1$ contains three integers $X_i$, $F_i$, $C_i$.

Output Format

Output a single integer, the minimum total cost.

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

9

Hint

Constraints

$1 \leq K \leq 10000$, $1 \leq E \leq 500$, $1 \leq N \leq 500$.

$0 < X_i < E$, $1 \leq F_i \leq 10000$, $1 \leq C_i \leq 10^7$.

Translated by ChatGPT 5