Валера очень любит свой сад, в котором растут n фруктовых деревьев.
В этом году будет большой урожай! На i-м дереве растут bi фруктов, все они созреют в день с номером ai. К сожалению, фрукты на дереве быстро портятся, поэтому собирать их можно только в день с номером ai и в день с номером ai + 1 (все фрукты, которые не собрали в эти два дня, становятся непригодными).
Валера не очень быстрый, но есть и позитивные моменты. Валера готов работать ежедневно. За один день Валера может собрать не более v фруктов. Фрукты могут быть как с одного дерева, так и с разных. Какое максимальное количество фруктов может собрать Валера за все время, если будет действовать оптимально?
Выходные данные
Выведите единственное целое число — максимальное количество фруктов, которое может собрать Валера.
Примечание
В первом примере, чтобы получить оптимальный ответ, нужно действовать следующим образом.
- Собрать в первый день 3 фрукта с 1-го дерева.
- Собрать во второй день 1 фрукт со 2-го дерева и 2 фрукта с 1-го дерева.
- В третий день собрать оставшиеся фрукты со 2-го дерева.
Во втором примере можно собрать только 60 фруктов, остальные фрукты просто пропадут.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
1 5
2 3
|
8
|
|
2
|
5 10
3 20
2 20
1 20
4 20
5 20
|
60
|