Buying Feed, II

Farmer John (FJ) needs to travel to town to buy $K$ pounds of feed ($1 \le K \le 100$). Driving $D$ miles with $K$ pounds of feed in his truck costs $D \times K$ cents.

The county feed lot has $N$ stores ($1 \le N \le 100$, conveniently numbered $1$ through $N$) that sell feed. Every store lies on a segment of the $X$ axis whose length is $E$ ($1 \le E \le 350$). Store $i$ is at location $X_i$ ($0 < X_i < E$) on the number line and can sell up to $F_i$ pounds ($1 \le F_i \le 100$) of feed at a price of $C_i$ cents ($1 \le C_i \le 1{,}000{,}000$) per pound. Remarkably, a single point on the $X$ axis may host more than one store.

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

What is the minimum amount FJ must pay to buy and transport the $K$ pounds of feed? A solution is guaranteed to exist.

• 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$ describing store $i$.

• Line $1$: A single integer, the minimum cost for FJ to buy and transport the feed.