Minimizing Total Expenditure in a Basketball League

In a basketball league, there are n teams. The season total expenditure for the i-th team is given by \(C_i\times x^2 + D_i\times y^2\), where \(x\) and \(y\) denote the number of wins and losses in the season respectively. It is guaranteed that \(D_i \le C_i\). At mid‐season, the i-th team has already accumulated \(a_i\) wins and \(b_i\) losses. There are still m matches to be played. In each match, one team wins and one team loses. The additional wins and losses can be distributed arbitrarily among the teams (subject to the global constraint that a total of m wins and m losses are added). Your task is to determine the minimum possible total expenditure of all teams over the entire season.

The final cost for team i becomes:

[ C_i\times (a_i+k_i)^2 + D_i\times (b_i+l_i)^2, ]

where \(k_i\) and \(l_i\) are the extra wins and losses allocated to team i, satisfying:

[ \sum_{i=1}^{n} k_i = m, \quad \sum_{i=1}^{n} l_i = m, \quad k_i, l_i \ge 0. ]

It is clear that the decision for wins and losses are independent. Since the cost functions are convex with respect to the extra wins (or losses), a greedy strategy can be applied: In each allocation (win or loss), choose the team with the smallest incremental cost, where the cost to award an extra win to team i (when it already has \(k_i\) extra wins) is:

[ \Delta_{win} = C_i\times\Bigl((a_i+k_i+1)^2-(a_i+k_i)^2\Bigr)= C_i\times (2(a_i+k_i)+1), ]

and similarly for losses:

[ \Delta_{loss} = D_i\times (2(b_i+l_i)+1). ]

Compute the minimal additional cost for wins and losses separately, add them to the initial costs \(\sum_{i=1}^{n}[C_i\times a_i^2 + D_i\times b_i^2]\), and output the overall minimal total expenditure.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5), denoting the number of teams and the number of remaining matches, respectively.

Then follow n lines, each containing four integers: ai bi Ci Di where ai and bi represent the current wins and losses of the i-th team, and Ci, Di are the expenditure coefficients with the guarantee that Di ≤ Ci.

outputFormat

Output a single integer—the minimum possible total season expenditure of all teams.

sample

2 1
1 0 3 2
0 1 5 4

14