Вор пробрался на склад спичек и хочет украсть как можно больше спичек. На складе находится m контейнеров, в контейнере номер i находится ai коробок спичек, а в каждой коробке bi спичек. Все коробки имеют одинаковый размер. В рюкзак вора помещается ровно n коробок. Ваша задача найти наибольшее количество спичек, которое сможет унести вор. У него нет времени на перекладывание спичек между коробками, поэтому он просто выбирает не более n коробок так, чтобы суммарное число спичек в них было максимальным.
Выходные данные
Выведите единственное число — ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 3
5 10
2 5
3 6
|
62
|
|
2
|
3 3
1 3
2 2
3 1
|
7
|