题目描述

一辆火车从 $1$ 号站出发，依次路过 $2$ 号站，$3$ 号站等等，最后停在 $n$ 号站。除最后一站外，每个站点都会都有一批新乘客，其中 $i$ 号站上有 $c_i$ 个人，他们的目的地是 $t_i$ 号站。火车的载客量有限，最多只能坐 $s$ 个人。当一批乘客下车后，座位空出来，可以继续接待下一批乘客。

火车必须沿编号顺序行驶，不能倒开。如果座位不足，可以选择只让一部分乘客上车，请问最多能满足多少乘客的要求？

输入格式

第一行：两个整数 $n$ 和 $s$； 第二行到第 $n$ 行：第 $i+1$ 行有两个整数 $t_i$ 和 $c_i$，分别表示第 $i$ 站乘客的目的地与数量。保证 $i<t_i\leq n$。

输出格式

单个整数：表示火车最多可以接待多少乘客。

5 100
4 80 
3 70
5 10
5 1

111

样例解释 1

1号站上车30人； 2号站上车70人； 3号站下车70人，上车10人； 4号站上车1人； 最后都在5号站下车。

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 50$，$1\leq s\leq 100$；
• 对于 $60\%$ 的数据，$1\leq n\leq 1000$，$1\leq s\leq 1000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq s\leq 10^7$，$0\leq c_i\leq 10^4$。