Buying Feed, II

Interview

Time limit1sMemory limit128 MB

Summary

Pick up to K pounds of feed from stores along a line, paying each store's price plus transport cost of distance carried, and minimize the total.

Level: Medium5 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Examples3

Example 1
Input
```
2 5 3
3 1 2
4 1 2
1 1 1
```
Expected output
```
7
```
Example 2
Input
```
5 10 2
5 3 1
1 10 1
```
Expected output
```
38
```
Example 3
Input
```
1 10 2
1 1 1
9 1 5
```
Expected output
```
6
```