B. Валера и фрукты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Валера очень любит свой сад, в котором растут n фруктовых деревьев.

В этом году будет большой урожай! На i-м дереве растут bi фруктов, все они созреют в день с номером ai. К сожалению, фрукты на дереве быстро портятся, поэтому собирать их можно только в день с номером ai и в день с номером ai + 1 (все фрукты, которые не собрали в эти два дня, становятся непригодными).

Валера не очень быстрый, но есть и позитивные моменты. Валера готов работать ежедневно. За один день Валера может собрать не более v фруктов. Фрукты могут быть как с одного дерева, так и с разных. Какое максимальное количество фруктов может собрать Валера за все время, если будет действовать оптимально?

Входные данные

В первой строке записано два целых числа через пробел n и v (1 ≤ n, v ≤ 3000) — количество фруктовых деревьев в саду и количество фруктов, которое Валера может собрать за один день.

В следующих n строках записано описание деревьев в саду. В i-й строке записано два целых целых числа через пробел ai и bi (1 ≤ ai, bi ≤ 3000) — день созревания фруктов на i-м дереве и количество фруктов на i-м дереве.

Выходные данные

Выведите единственное целое число — максимальное количество фруктов, которое может собрать Валера.

Примеры
Входные данные
2 3
1 5
2 3
Выходные данные
8
Входные данные
5 10
3 20
2 20
1 20
4 20
5 20
Выходные данные
60
Примечание

В первом примере, чтобы получить оптимальный ответ, нужно действовать следующим образом.

  • Собрать в первый день 3 фрукта с 1-го дерева.
  • Собрать во второй день 1 фрукт со 2-го дерева и 2 фрукта с 1-го дерева.
  • В третий день собрать оставшиеся фрукты со 2-го дерева.

Во втором примере можно собрать только 60 фруктов, остальные фрукты просто пропадут.