Buying Feed

Farmer John (FJ) must travel to town to pick up $K$ ($1 \le K \le 10\,000$) pounds of feed. Driving $1$ mile while carrying $K$ pounds of feed costs $K \times K$ cents; driving $D$ miles with the same load costs $D \times K \times K$ cents.

FJ can buy feed from any of $N$ ($1 \le N \le 500$) stores, numbered $1 \ldots N$. All stores sit on a segment of the X axis of length $E$ ($1 \le E \le 500$) miles. Store $i$ is at location $X_i$ ($0 < X_i < E$) and sells feed at $C_i$ ($1 \le C_i \le 10\,000\,000$) cents per pound, up to $F_i$ ($1 \le F_i \le 10\,000$) pounds. More than one store may share the same location.

FJ starts at location $0$ and can drive only in the positive direction, finishing at location $E$ carrying at least $K$ pounds of feed. Along the way he may stop at any store and buy any amount up to that store's limit.

What is the minimum total amount FJ must pay to buy and transport $K$ pounds of feed? It is guaranteed that the stores together can supply enough feed.

For example, suppose FJ needs $2$ pounds and there is one store at each of the locations $1$, $3$, and $4$ on a number line spanning $0 \ldots 5$:

      0   1   2   3   4   5   X
      +---|---+---|---|---+
          1       1   1
          1       2   2

Under each store, the first row of numbers is how many pounds it can sell and the second row is its price in cents per pound. So the store at location $1$ sells $1$ pound for $1$ cent, and the stores at locations $3$ and $4$ each sell $1$ pound for $2$ cents.

The cheapest plan is to buy $1$ pound from the store at location $3$ and $1$ pound from the store at location $4$. The feed costs $2 + 2 = 4$ cents. Driving from $0$ to $3$ costs nothing because FJ carries no feed. Driving from $3$ to $4$ moves $1$ pound over $1$ mile, costing $1 \times 1 \times 1 = 1$ cent; driving from $4$ to $5$ moves $2$ pounds over $1$ mile, costing $1 \times 2 \times 2 = 4$ cents. The total is $4 + 1 + 4 = 9$ cents.

• Line $1$: three space-separated integers $K$, $E$, and $N$.
• Lines $2$ to $N+1$: line $i+1$ contains three space-separated integers $X_i$, $F_i$, and $C_i$.

• A single integer: the minimum total cost for FJ to buy and transport the feed.