There are $n$ locations on a straight line. The $i$-th location has coordinate $x_i$ and stores $a_i$ units of goods.

You can build at most $p$ logistics warehouses at these locations. The cost to build a warehouse at location $i$ is $c_i$. If a location $i$ does not have a warehouse, all goods stored at that location must be moved to the nearest warehouse. Moving $a_i$ units of goods to a warehouse at distance $f$ incurs a cost of $a_i \cdot f$.

Logistics Warehouse Location Problem: Determine a plan for building logistics warehouses such that the total cost is minimized.

Input

Each test case contains multiple test sets.

The first line of the input contains two integers $n$ and $p$.

The next $n$ lines each contain three integers $x_i, a_i, c_i$.

Output

For each test set, output a single integer representing the answer.

Examples

Input 1

7 3
1 4 3
2 4 3
3 6 5
4 1 1
5 5 7
6 3 7
9 8 7
4 2
1 2 6
6 2 9
7 2 6
9 2 2
3 2
2 9 1
5 4 6
8 3 3

Output 1

31
18
16

Subtasks

For $30\%$ of the data, $n \leq 10\,000$.

For $100\%$ of the data, $p \leq n \leq 1\,110\,000$, $1 \leq x_i, c_i, a_i \leq 10^6$, and $x_1 \leq x_2 \leq \cdots \leq x_n$.

Note

1. The number of test sets was not provided during the contest; "please evaluate for yourself."
2. No memory limit was provided during the contest; it is set to 1 GB on QOJ.