← 返回题目列表

Codeforces · 441/B

B. 瓦莱拉和水果

中文机器翻译题面 查看原题

瓦莱拉喜欢他的花园,那里生长着 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个水果,剩下的水果就会枯萎。