题目描述

有一家牧场每天都会产出牛奶，在第 i 天，牛奶的产量为 pi。批发商每天都会上门来收购，在第 i 天，收购量为 ci。如果某天收购量不大，多余的牛奶就会放进冷库保存。牛奶有一个保鲜期，如果超过了 m 天 （m 为一个给定的整数），就必须倒掉了。卖给批发商时，应该先卖冷藏时间长的牛奶。

给定天数 n 以及每天的牛奶产量和收购量，请求出牧场一共可以卖出多少量的牛奶。注意若某天的收购量很大，超过了当时可卖的总量，则当天卖出的牛奶数量就是可卖的总量。

输入格式

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

输出格式

单个整数表示答案。

数据范围

对于 30% 的数据，1≤n,m≤1000；

对于 60% 的数据，1≤n,m≤10000；

对于 100% 的数据，1≤n,m≤100000；

0≤pi,ci≤10000。

样例数据

输入:

5 2

50 0

100 0

250 0

300 0

1000 5000

输出:

1550

说明:

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

输入:

5 5

0 2

2 3

5 0

3 0

2 0

输出:

2