题目描述

可爱村只有一条长长的街道，从东向西延伸，有 $m$ 户人家。每栋房子都有一个单独的房号，从 $1$ 开始到 $m$ 结束。

最近的暴风雪摧毁了大部分电话线，所以市长出资建造了一个新的电话线。Mirko 对这个新的电话网络的普及程度很感兴趣，所以他在一些点上安装了特殊的探测器。

探测器可以检测到两栋房子之间的任何通话，但必须满足其中一栋房子在探测器的 东边，另一栋房子在探测器的 西边。

在第一个月结束时，Mirko 撤掉了所有的探测器，并记录了每个探测器检测到的通话数量。现在想知道在这一个月里，可能的最小 通话数量是多少。

输入格式

第一行，两个正整数，$n, m$，分别表示探测器和房屋的数量。

接下来，$n$ 行，每行两个正整数 $P_i$，和 $C_i$，表示编号为 $i$ 的探测器的位置和通话总数。 其中 $P_i$ 表示探测器在编号为 $P_i$ 和 $P_i+1$ 的房屋之间。

同一位置上最多有一个探测器。

输出格式

输出一个正整数，表示最小的通话次数。

样例 #1

样例输入 #1

3 4
3 1
2 2
1 1

样例输出 #1

2

样例 #2

样例输入 #2

2 3
1 23
2 17

样例输出 #2

23

样例 #3

样例输入 #3

3 9
7 2
8 3
3 4

样例输出 #3

5

提示

数据规模及约定

• 对于 $50\%$ 的数据，$1 \le n \le 10^3$，$1 \le C_i \le 10^3$，$n < m \le 10^9$，$1 \le P_i < M$。
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le C_i \le 10^9$，$n < m \le 10^9$，$1 \le P_i < M$。