在一个按照南北方向划分成规整街区的城市里，n个居民点分布在一条直线上的n个坐标点x1 <……< xn处。居民们希望在城市中至少选择 1个，但不超过k 个居民点建立服务机构。在每个居民点i x 处，服务需求量为w_i >=0，在该居民点设置服务机构的费用为 c _i>=0。
假设居民点x_i 到距其最近的服务机构的距离为 d_i ，则居民点x_i 的服务费用为w_i * d _i。建立k 个服务机构的总费用为A+B。A 是在k 个居民点设置服务机构的费用的总和；B是n个居民点服务费用的总和。

对于给定直线L 上的n 个点 x₁ <……< x_n ，计算在直线L 上最多设置k 处服务机构的最小总费用。

输入数据第1 行有2 个正整数n和k。n表示直线L 上有n 个点n x1 <……< x ；k 是服务机构总数的上限。接下来的n行中，每行有 3 个整数。第 i+1行的 3个整数 x_i ,w_i , c_i，分别表示相应居民点的位置坐标，服务需求量和在该点设置服务机构的费用。

将计算的最小服务费用输出