Шоколад помогает развивать ум и укреплять дух! Старец Летовец после своих занятий угощает своих учеников шоколадом. На следующем занятии у него будет M учеников и каждому из них Старец хочет дать по одной плитке шоколада.
Чтобы купить нужное количество шоколада, старец отправил своего праправнука Летовёнка разузнать, какое минимальное количество денег ему понадобится.
Оказывается, каждый магазин продаёт шоколад по разной цене. В i-м магазине можно купить не более Bi плиток шоколада по цене Аi рублей за плитку. Летовец хочет потратить как можно меньше денег, но при этом купить ровно M плиток шоколада.
Помогите Летовёнку посчитать какую минимульную сумму на шоколад потратит старец Летовец.
Формат входных данных
В первой строке заданы два числа:
N и
M (1 <= N, M <= 10
5). Следующие
N строк содержат по 2 числа:
Ai (1 <= A
i <= 10
9) и
Bi (1 <= В
i <= 10
5).
\(B_1 + B_2 +... + B_N >= M\).
Формат выходных данных
Выведите минимальную сумму денег, необходимую для покупки
M плиток шоколада.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 5
4 9
2 4 |
12 |
| 2 |
4 30
6 18
2 5
3 10
7 9 |
130 |
| 3 |
1 100000
1000000000 100000 |
100000000000000 |