P4544 [USACO10NOV] Buying Feed G

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: |Coordinate|$X=1$|$X=3$|$X=4$|$E=5$| |:-:|:-:|:-:|:-:|:-:| |Stock|$1$|$1$|$1$| |Price|$1$|$2$|$2$| 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.

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 a single integer, the minimum total cost.

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