U121090 [FJOI2020]物流仓库选址问题

一条直线上有 $n$ 个物流仓库，要求在这 $n$ 个仓库中选择 $p$ 个作为货物集散地，所有仓库的货物都需要运输到货物集散地。 对于每个仓库有 $x_i,a_i,c_i$ ，分别表示该仓库的坐标 $(x_i,0)$ ，货物运输单位距离所需的费用及建设货物集散地的费用。 求一个选择 $p$ 个货物集散地的方案，使所有货物运输到货物集散地及建设货物集散地的总费用最小，输出这个最小的费用。

输入包含多组数据。 对于每组数据： 第一行 $2$ 个数 $n,p$ ，意义如题目描述所示。 接下来 $n$ 行，第 $i+1$ 行 $3$ 个数 $x_i,a_i,c_i$ ，意义如题目描述所示。

对于每组数据，输出 $1$ 行，包含 $1$ 个数，表示所有货物运输到货物集散地及建设货物集散地的最小总费用。

对于 $100\%$ 的数据，$p\leq n\leq 1100005$ 。