Minimum Highway Construction Cost

There are n towns that need to be connected by exactly m highways, forming a connected network. Each highway connects two different towns and is constructed collaboratively by the two towns it connects. In particular, if a town builds its j-th highway (in the order of its construction tasks), then the cost incurred by that town for that highway is given by the formula: \(a_i j^2 + b_i j + c_i\), where \(a_i\), \(b_i\), and \(c_i\) are parameters specific to town i.

The overall cost is the sum of the construction costs incurred by each town. Note that because each highway is jointly built by the two towns it connects, each town is responsible for one half of every highway incident to it. To ensure the entire network is connected, every town (when n > 1) must build at least one highway. Thus an optimal construction plan must choose exactly m highways such that:

• The undirected graph is connected.
• The total cost, determined by the sum over all towns of \[ \text{cost}_i = \sum_{j=1}^{d_i} (a_i j^2 + b_i j + c_i), \] is minimized, where \(d_i\) is the number of highways that town i is responsible for. Since the network has m highways and each highway contributes to the cost of two towns, the degrees must satisfy \[ \sum_{i=1}^n d_i = 2m \quad \text{and} \quad d_i \ge 1 \text{ for all } i \text{ (if } n>1\text{)}. \]

A useful observation is that the cost incurred by each town is independent once the number of highways it builds is fixed. In an optimal plan, every town will construct its first highway (to ensure connectivity) incurring a base cost of \(a_i\cdot1^2 + b_i\cdot1 + c_i\), and the remainder of the extra highway constructions (if any) will be allocated in a greedy manner based on the incremental cost. For town i, if it has already built e extra highways (beyond the mandatory first one), the next highway will cost an additional \[ \Delta_i(e) = a_i (e+2)^2 + b_i (e+2) + c_i. \] By starting with each town’s base cost and using a greedy strategy to allocate the extra \(L = 2m - n\) highways (since each town must at least contribute one highway), the optimal total cost can be computed.

inputFormat

The first line contains two integers n and m. For n > 1, it is guaranteed that m \(\geq\) n - 1.

Then follow n lines, each containing three integers: \(a_i\), \(b_i\), and \(c_i\) for the i-th town.

outputFormat

Output a single integer representing the minimum total construction cost to build the highway network.

sample

3 2
1 2 3
2 1 1
1 1 1

23