直线k中值问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在一个按照南北方向划分成规整街区的城市里,n个居民点分布在一条直线上的n个坐标点x1 <……< xn处。居民们希望在城市中至少选择1个,但不超过k 个居民点建立服务机构。在每个居民点 xi 处,服务需求量为 wi≥0 ,在该居民点设置服务机构的费用为 ci≥0。假设居民点 xi  到距其最近的服务机构的距离为 di ,则居民点 xi  的服务费用为 wi × di
建立k 个服务机构的总费用为A+B。A 是在k 个居民点设置服务机构的费用的总和;B是n个居民点服务费用的总和。
对于给定直线L 上的n 个点x1 <……< xn ,计算在直线L 上最多设置k 处服务机构的最小总费用。

Input

输入数据的第1 行有2 个正整数n和k(n≤500,k≤250)。n表示直线L 上有n 个点x1 <……< xn ;k 是服务机构总数的上限。接下来的n行中,每行有3 个整数。第i+1行的3个整数xi  , wi ,  ci ,分别表示相应居民点的位置坐标,服务需求量和在该点设置服务机构的费用。

Output

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

Sample Input

9 3
2 1 2
3 2 1
6 3 3
7 1 1
9 3 2
15 1 6
16 2 1
18 1 2
19 1 1

Sample Output

19

Hint

Source