题目描述

Hearing that energy drinks increase rating in those sites, Takahashi decides to buy up $M$ cans of energy drinks.

There are $N$ stores that sell energy drinks. In the $i$-th store, he can buy at most $B_i$ cans of energy drinks for $A_i$ yen (the currency of Japan) each.

What is the minimum amount of money with which he can buy $M$ cans of energy drinks?

It is guaranteed that, in the given inputs, a sufficient amount of money can always buy $M$ cans of energy drinks.

听说能量饮料能提高这些网站的收视率，高桥决定购买 $M$ 罐能量饮料。

有 $N$ 家商店出售能量饮料。在 $i$ th商店，他最多可以买到{846445519}罐能量饮料，每罐 $A_i$ 日元（日本货币）。

他最少可以用多少钱购买 $M$ 罐能量饮料？

在给定的投入中，保证足够的钱总是可以买到 $M$ 罐能量饮料。

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

打印高桥可以购买 $M$ 罐能量饮料的最低金额。

样例 #1

样例输入 #1

2 5
4 9
2 4

样例输出 #1

12

样例 #2

样例输入 #2

4 30
6 18
2 5
3 10
7 9

样例输出 #2

130

样例 #3

样例输入 #3

1 100000
1000000000 100000

样例输出 #3

100000000000000

说明

数据规模与约定

• 所有输入值均为整数。
• $1 \leq N, M \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^5$
• $B_1 + ... + B_N \geq M$

样例 $1$ 解释

用 $12$ 日元，我们可以在第一家商店买一杯饮料，在第二家商店买四杯饮料，总共买五杯饮料。但是，我们不能用 $11$ 日元或更少的钱购买 $5$ 种饮料。

样例 $3$ 解释

输出可能不适合 $32$ （位）整数类型。