Почувши, що енергетичні напої підвищують свої рейтинги в мережі, Степан вирішує купити \(M\) банок енергетичних напоїв.

Є \(N\) магазинів, які продають енергетичні напої. У \(i\)-му магазині він може купити щонайбільше \(B_i\) ​ банок напоїв за \(A_i\) ​гривень за кожну.

За яку мінімальну суму він може купити \(M\) банок?

Гарантовано, що при наших вхідних даних за достатню суму грошей завжди можна купити \(M\) банок енергетичних напоїв.

Формат вхідних даних

Перший рядок вхідного потоку містить два цілі числа \(N,M\) (\(1 \le N,M \le 10^5\)).

Наступні \(N\) рядків містять пари цілих чисел \(A_i, B_i\) (\(1 \le A_i \le 10^9\), \(1 \le B_i \le 10^5\), \(M \le B_1 + ... + B_N\) ). Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану мінімальну суму.

Примітка

До прикладу 1:

За 12 грн ми можемо купити один напій у першому магазині та чотири напої в другому магазині, разом буде п’ять. Ми не зможемо купити 5 напоїв за 11 грн або менше.

Приклад вхідних даних

2 5
4 9
2 4

Приклад вихідних даних

12

Приклад вхідних даних

4 30
6 18
2 5
3 10
7 9

Приклад вихідних даних

130

Приклад вхідних даних

1 100000
1000000000 100000

Приклад вихідних даних

100000000000000