Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает купить
M плиток шоколада. В городе есть
N магазинов, которые продают различный шоколад. В
i-м магазине Василий может купить не более
Bi плиток шоколада по
Ai рублей каждая. Помогите Василию определить, какую минимальную сумму денег ему необходимо накопить, чтобы купить
M плиток шоколада?
Гарантируется, что располагая нужной суммой, Василий всегда сможет купить
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 |