Minimum Cost Feed Transportation

Farmer John needs to travel from location 0 to location \(E\) along a straight road. He must purchase exactly \(K\) pounds of feed along the way. There are \(N\) stores on the road (numbered arbitrarily) where each store \(i\) is located at position \(X_i\) with a maximum supply of \(F_i\) pounds of feed available at a cost of \(C_i\) cents per pound.

Whenever Farmer John drives a distance \(D\) while carrying \(X\) pounds of feed, the transportation cost incurred is \(D \times X\) cents. He starts at position 0 with no feed, and he travels only in the positive direction in order to finally reach position \(E\) with at least \(K\) pounds of feed. At any store, he may purchase any amount (up to the store's limit) of feed. The goal is to determine the minimum total cost, which is the sum of the purchasing cost and the transportation cost.

The cost components:

• Purchase cost: If Farmer John buys \(x\) pounds of feed at a store with price \(C_i\) cents per pound, he pays \(x \times C_i\) cents.
• Transportation cost: Suppose he travels a distance \(D\) with \(X\) pounds of feed in the truck, the cost is \(D \times X\) cents.

It is guaranteed that there is a viable way for Farmer John to obtain \(K\) pounds of feed.

Example:

Input:
2 5 3
1 1 1
3 1 2
4 1 2
Explanation:
There are 3 stores at positions 1, 3, and 4. The available feed and costs (per pound) are as follows:

Store at 1: 1 pound available at 1 cent
Store at 3: 1 pound available at 2 cents
Store at 4: 1 pound available at 2 cents

It is optimal for Farmer John to purchase one pound at the store located at 3 and one pound at the store located at 4.
Cost breakdown:

Purchase cost: 2 + 2 = 4 cents
Transportation cost: from 3 to 4 carrying 1 pound = 1 cent, and from 4 to 5 carrying 2 pounds = 2 cents
Total cost = 4 + 1 + 2 = 7 cents.
</pre>

inputFormat
The first line contains three integers \(K\) (1 ≤ \(K\) ≤ 100), \(E\) (1 ≤ \(E\) ≤ 350), and \(N\) (1 ≤ \(N\) ≤ 100) — the pounds of feed needed, the length of the road, and the number of stores, respectively.
Each of the next \(N\) lines contains three integers \(X_i\) (0 < \(X_i\) < \(E\)), \(F_i\) (1 ≤ \(F_i\) ≤ 100), and \(C_i\) (1 ≤ \(C_i\) ≤ 1,000,000), representing the store's position, the maximum available feed at that store, and the cost per pound in cents, respectively.
You may assume that it is always possible for Farmer John to accumulate exactly \(K\) pounds of feed by the time he reaches location \(E\).
outputFormat
Output a single integer — the minimum total cost (in cents) for Farmer John to purchase and transport \(K\) pounds of feed to his destination at location \(E\).
sample
2 5 3
1 1 1
3 1 2
4 1 2
7