1767:销售牛奶

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:12 解决:6

题目描述

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

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

输入

第一行:两个整数 $n$ 和 $m$

第二行到第 $n+1$ 行: 第 $i+1$ 行每行两个整数分别表示 $p_i, c_i$

$1\le n,m\le 10^5; 0\le p_i,c_i\le 10^4$

输出

单个整数表示答案。

样例输入-1 复制

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

样例输出-1 复制

1550