Valera and Fruits

题意翻译

Valera很爱他的花园，因为那里生长着n棵果树。 今年他将迎来一场大丰收！第i棵树上会结出bi个果实，它们将在第ai天全部成熟。不幸的是，这些果子将很快枯萎，因此Valera只能在第ai天和第ai+1天摘下它们。（所有不在指定的两天内摘下的果子，都不可食用） Valera的动作不是很快，但他也有自己的优势。他已经准备好了，以保证每天都可以工作。一天，Valera最多可以摘下v个果子，这些果子有可能是同一棵树上的，也有可能不是。那么，在合理安排日程表的情况下，Valera最多可以收获多少个果子？ 输入格式： 第1行包含两个用空格隔开的整数，n和v（1 <= n,v <= 3000）——即花园里一共有多少棵树，以及Valera一天最多可以摘下多少个果子。 第2~n+1行包含对于每一棵树的具体描述。第i+1行会包含两个用空格隔开的整数，ai和bi（1 <= ai,bi <= 3000）——即第i棵树上的果子会在哪一天完全成熟，以及第i棵树上会结出多少个果子。 输出格式： 输出一个整数——即Valera所能收获的果子的最大值。

题目描述

Valera loves his garden, where $ n $ fruit trees grow. This year he will enjoy a great harvest! On the $ i $ -th tree $ b_{i} $ fruit grow, they will ripen on a day number $ a_{i} $ . Unfortunately, the fruit on the tree get withered, so they can only be collected on day $ a_{i} $ and day $ a_{i}+1 $ (all fruits that are not collected in these two days, become unfit to eat). Valera is not very fast, but there are some positive points. Valera is ready to work every day. In one day, Valera can collect no more than $ v $ fruits. The fruits may be either from the same tree, or from different ones. What is the maximum amount of fruit Valera can collect for all time, if he operates optimally well?

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ v $ $ (1<=n,v<=3000) $ — the number of fruit trees in the garden and the number of fruits that Valera can collect in a day. Next $ n $ lines contain the description of trees in the garden. The $ i $ -th line contains two space-separated integers $ a_{i} $ and $ b_{i} $ $ (1<=a_{i},b_{i}<=3000) $ — the day the fruits ripen on the $ i $ -th tree and the number of fruits on the $ i $ -th tree.

输出格式

Print a single integer — the maximum number of fruit that Valera can collect.

输入输出样例

输入样例 #1

2 3
1 5
2 3

输出样例 #1

8

输入样例 #2

5 10
3 20
2 20
1 20
4 20
5 20

输出样例 #2

60

说明

In the first sample, in order to obtain the optimal answer, you should act as follows. - On the first day collect $ 3 $ fruits from the $ 1 $ -st tree. - On the second day collect $ 1 $ fruit from the $ 2 $ -nd tree and $ 2 $ fruits from the $ 1 $ -st tree. - On the third day collect the remaining fruits from the $ 2 $ -nd tree. In the second sample, you can only collect $ 60 $ fruits, the remaining fruit will simply wither.