K个工人受雇粉刷一圈篱笆，篱笆由N块木板组成，从左到右依次编号为1..N。工人i (1<=i<=K) 站在木板Si前面，他可以选择不粉刷木板，当然他也就得不到任何收入；否则，他必须粉刷一个区间内的所有木板，这个区间内最多有Li块木板，并且一定要包含Si在内。当工人i完成了粉刷任务以后，对于他粉刷的每块木板，都能获得报酬Pi。由于雇主讨厌重复而无意义的劳动，所以一块木板最多只能粉刷一次。因此，这K个工人所要粉刷的区间必须没有任何重叠部分。现在就请你来计算一下，应该怎么安排这K个工人各自粉刷的区间，才能使得他们的收入总和最高。

输入数据：


输出数据：
仅一个整数——工人们的最大收入总和。

说明：
1 <=N <=16 000
1 <=K <=100
1 <=Pi <=10 000
1 <=Li , Si <=N
所有的Si均不相同
不一定非要把所有的N块木板都粉刷完毕

样例：