题目描述

有一个用户，在连续的 $n$ 天里，都会收到积分，也会使用积分。这些积分有效期为 $m$ 天（$m$ 为一个给定的整数），若超过了 ，积分就失效了。

在第 $i$ 天，用户将会获得 $p_i$ 分，他需要消费 $c_i$ 分（若积分不足，则用掉全部积分后用其他方式消费）。使用积分时，应先用掉最早的。

请计算这个用户一共可以用掉多少积分。

输入格式

• 第一行：两个整数 $n$ 和 $m$；
• 第二行到第 $n+1$ 行：第 $i+1$ 行每行两个整数表示 $p_i$ 和 $c_i$。

输出格式

• 单个整数表示答案。

数据范围

• 对于 $30\%$ 的数据，$1\leq n,m\leq 1000$；
• 对于 $60\%$ 的数据，$1\leq n,m\leq 10000$；
• 对于 $100\%$ 的数据，$1\leq n,m\leq 100000$；
• $0\leq p_i, c_i\leq 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