Hedgehogs communicate via complex calls. Hedgehogs with better calls can communicate a longer distance. Consider n Hedgehogs (working together) on the X-axis, with coordinates Xi for 1 ≤ i ≤ n, and communication ability Ai, then 2 hedgehogs can communicate if and only if |Xi + Xj| ≤ Ai + Aj. Exactly k hedgehogs are not underground looking for food, and can currently communicate and lookout for attacking Eagles. The remaining n − k hedgehogs are foraging for food. The units of food each hedgehog can forage underground each day is given by Si. Each Hedgehog that is communicating can increase their communication ability Ai by D from consuming D unit of food. Compute the minimal food cost on any given day for all pairs of hedgehogs to be able to communicate directly. If there is food surplus, just print a negative integer indicating negative food cost. Input A number of of inputs (≤ 50), each starting with two integers n and k are given (1 ≤ k ≤ n ≤ 100000). On each of the following n lines are Xi, Ai, Si (1 ≤ Xi, Ai, Si ≤ 1000000000). Output For each input, output the minimal food cost (or maximal gain). In case of a gain, the printed number should be negative. Sample Input 53 41 632 33 131 22 43 871 32 93 1211 62 153 1593 52 21 Sample Output 412