Missile Collision Countermeasure

In this problem, you are given (n) missiles. The (i)-th missile is initially suspended at ((x_i, y_i)) with an initial horizontal velocity (v_i). All missiles start their projectile (horizontal) motion simultaneously. The gravity (g) is (9.8) (acting in the negative (y) direction). Thus, the landing time for the (i)-th missile is [ T_i = \sqrt{\frac{2y_i}{9.8}}. ] When a missile lands (i.e. touches the (x) axis) it gains an extra explosion power of (1). In addition, for any two distinct missiles that collide during flight, each missile involved in the collision gains an extra (1) point in explosion power. Note that two missiles can only collide in mid‐air if and only if they have the same initial height (y_i), and there exists a time (t) with (0 < t < T_i = \sqrt{\frac{2y_i}{9.8}}) such that [ x_i + v_i,t = x_j + v_j,t \quad \text{and} \quad y_i = y_j. ] (If (v_i = v_j) and (x_i \neq x_j), they will never meet.)

Thus, for each missile (i), let its explosion power be defined as [ p_i = (\text{number of mid-air collisions involving missile } i) + 1. ]

After computing the explosion power values, the ground command deploys counter-weapons. For the (i)-th missile, there is an associated countermeasure which can reduce its explosion power by (a_i) (to a minimum of 0); however, due to technical limitation, you may only activate the countermeasure on at most (m) missiles. That is, if you activate the countermeasure for missile (i), its final explosion damage becomes (\max(p_i - a_i, 0)); otherwise, it remains (p_i).

Your task is to choose at most (m) missiles on which to apply the countermeasure so that the total explosion damage, which is the sum of the final explosion damages of all missiles, is minimized. Compute this minimum total damage.

Note that the gain from applying a countermeasure to missile (i) is (\min(p_i, a_i)) (since the damage cannot go below 0). Therefore, the optimal strategy is to choose the (m) missiles with the largest values of (\min(p_i, a_i)).

inputFormat

The first line contains two integers (n) and (m) ( (1 \leq n \leq 10^5), (0 \leq m \leq n) ), representing the number of missiles and the number of countermeasures that can be activated. Each of the following (n) lines describes a missile with four numbers: (x_i, y_i, v_i, a_i). Here, (x_i) and (y_i) are the coordinates of the missile, (v_i) is its initial horizontal velocity, and (a_i) is the reduction amount of the countermeasure for that missile. It is guaranteed that (y_i > 0).

outputFormat

Output a single number: the minimum total explosion damage after optimally applying at most (m) countermeasures.

sample

3 1
0 10 10 5
5 10 0 3
10 20 -5 4

3