Minimum Cost to Fill the Truck

Little Blue is responsible for the raw material purchasing for a factory. The factory has a truck with a capacity of m units. There are n supply points located on the same road and in the same direction from the factory, each at a different distance. The i-th supply point offers raw material at a price of \(a_i\) per unit, has an available stock of \(b_i\) units, and is located at a distance of \(c_i\) from the factory.

For every unit distance the truck travels, an extra cost of o is incurred. (Note that there is no travel cost on the return trip; you can also think of o as being half the cost of travelling two units of distance.)

The goal is to purchase exactly m units to completely fill the truck while minimizing the total cost. The total cost is the sum of the material cost and the travel cost. Importantly, the travel cost is determined by the furthest supply point that you purchase from, i.e. if the maximum distance among the chosen supply points is \(L\), then the travel cost is \(L \times o\); the factory is at position 0. If it is not possible to purchase m units due to insufficient stock, output -1.

Note on Strategy: Since the supply points lie along a single direction, if you decide to buy at a point located at \(c_i\), you will incur a travel cost of \(c_i \times o\) regardless of whether you also purchase on an earlier point. Hence, an optimal strategy is to select a furthest supply point (with distance \(L\)) such that the total available stock from supply points with distances not exceeding \(L\) is at least m, and then purchase the raw materials in a cost-minimizing way from these points (by buying from the cheaper ones first).

inputFormat

The first line contains three integers: n m o (n is the number of supply points, m is the capacity of the truck, and o is the cost per unit distance traveled).

The following n lines each contain three integers: ai bi ci, where ai is the unit price at the i-th supply point, bi is the available stock, and ci is the distance from the factory.

outputFormat

Output a single integer: the minimum total cost to fill the truck. If it is not possible to fill the truck with m units, print -1.

sample

3 10 1
5 5 1
6 6 2
1 5 3

33