问题 E: 牛奶供应(一)

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:6 解决:6

题目描述

有一家牧场每天都会产出牛奶,在第 i 天,牛奶的产量为 ��pi。生产的牛奶可以卖到市场上,在第 i 天,市场需求为 ��ci。如果市场需求不大,卖不掉牛奶,则多余的牛奶就会放进冷库保存。牛奶有一个保鲜期,如果超过了 m 天 (m 为一个给定的整数),就必须倒掉了。卖牛奶时,应先卖冷藏时间长的。

给定天数 n 以及每天的产量和收购量,请求出牧场一共可以卖出多少牛奶。

输入

第一行:两个整数 n 和 m
第二行到第 �+1n+1 行:第 �+1i+1 行每行两个整数表示 ��pi 和 ��ci

  • 对于 30%30% 的数据,1≤�,�≤10001n,m1000
  • 对于 60%60% 的数据,1≤�,�≤100001n,m10000
  • 对于 100%100% 的数据,1≤�,�≤1000001n,m100000
  • 0≤��,��≤100000pi,ci10000





输出

单个整数表示答案。

样例输入 复制

5 2
50 0
100 0
250 0
300 0
1000 5000

样例输出 复制

1550

提示

最后一天的收购量很大,但第一天和第二天的牛奶由于过期不能出售了


提示:
可以尝试双指针方法


某些朱姓的人建议:可以从生产量开始逐步从当前天往后一一销售,知道第一m天。