一条直线上有 $n$ 个地点，第 $i$ 个地点的坐标为 $x_i$，且存放了总量为 $a_i$ 的货物。

你可以在不超过 $p$ 个地点处建设物流仓库。在第 $i$ 个地点建设物流仓库的代价是 $c_i$。随后如果一个地点 $i$ 处没有建设物流仓库，那么则需要将所有在该地点存放的货物移动到与其最接近的物流仓库内。将总量为 $a_i$ 的货物移动到距离其 $f$ 的仓库需要付出 $a_i \cdot f$ 的代价。

物流仓库选址问题：制定一个建设物流仓库的方案，使得最终得到的总代价最小。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含两个整数 $n, p$。

接下来 $n$ 行，每行包含三个整数 $x_i, a_i, c_i$。

输出格式

对于每组测试数据，输出一行一个整数，表示答案。

样例数据

样例输入

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

样例输出

31
18
16

子任务

对于 $30\%$ 的数据，$n \leq 10\,000$。

对于 $100\%$ 的数据，$p\leq n \leq 1\,110\,000$，$1 \leq x_i,c_i,a_i \leq 10^6$，$ x_1 \leq x_2 \leq \cdots \leq x_n$。

注

1. 赛时并未提供数据组数，“请选手自行评估”。
2. 赛时并未提供空间限制，“请选手自行评估” QOJ 上设置为 1 GB。