瓦莱拉喜欢他的花园,那里生长着 n 棵果树。
今年他会大丰收!在第 i 棵树上长出 bi 果实,它们将在第 ai 天成熟。不幸的是,树上的果实枯萎了,所以只能在ai日和ai+1日采集(这两天没有采集到的所有果实都变得不适合吃)。
Valera 的速度不是很快,但也有一些积极的地方。瓦莱拉每天都准备好工作。一天之内,瓦莱拉最多只能收集 v 个水果。果实可能来自同一棵树,也可能来自不同的树。如果瓦莱拉操作得当,他最多可以收集多少水果?
输入
第一行包含两个空格分隔的整数 n 和 v (1 ≤ n, v ≤ 3000) — 花园中果树的数量以及 Valera 一天可以采集的水果数量。
接下来的 n 行包含花园中树木的描述。第 i 行包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ 3000) — 第 i 棵树上的果实成熟的日期以及第 i 棵树上的果实数量。
输出
打印一个整数——Valera 可以收集的最大水果数量。
示例
输入 #1
2 3 1 5 2 3
输出 #1
8
输入 #2
5 10 3 20 2 20 1 20 4 20 5 20
输出 #2
60
注意
在第一个示例中,为了获得最佳答案,您应该执行以下操作。
- 第一天从第一棵树上收集 3 个水果。
- 第二天从第二棵树上收集 1 个水果,从第一棵树上收集 2 个水果。
- 第三天从第二棵树上收集剩余的水果。
在第二个样本中,你只能收集60个水果,剩下的水果就会枯萎。