John's Feed Transportation Optimization

John drives into town to buy feed. He needs to bring K tons of feed home. While driving, the transportation cost is quadratic: if the car is carrying X tons, it costs \(D \times X^2\) yuan to drive D kilometers.

There are N stores along a one‐dimensional axis. The i-th store is located at coordinate \(X_i\), selling feed at \(C_i\) yuan per ton with a stock of \(F_i\) tons.

John starts at \(X=0\) and his home is at \(X=E\) (with \(E > 0\)). He may buy feed at any of the stores along the way. The total available feed is guaranteed to be at least K tons. Determine the minimum total cost, which is the sum of the purchasing cost and the transportation cost.

For example, consider 3 stores:

If K = 2, John may choose to buy from the two stores closest to his home, with a road cost of \(1+4=5\) and a purchase cost of \(2+2=4\), totalling 9 yuan.

inputFormat

The first line contains three integers: N, K, and E where N is the number of stores, K is the required tons of feed, and E is the coordinate of John's home.

Each of the following N lines contains three integers \(X_i\), \(F_i\), and \(C_i\) representing the position of the store, the available feed stock, and the cost per ton respectively.

outputFormat

Output a single integer, the minimum total cost required to bring exactly K tons of feed home.

sample

3 2 5
1 1 1
3 1 2
4 1 2

9