题目描述

Aki 要买恰好 $M$ 瓶饮料。现在有 $N$ 家商店，第 $i$ 家商店的饮料单价为 $a_i$ 元，最多可以购买 $b_i$ 瓶。
数据保证所有商店的总库存不少于 $M$，即 $\sum b_i \ge M$。
Aki 希望在买到恰好 $M$ 瓶饮料的前提下，使得总花费最小。请你帮他计算最小总花费。

输入格式

第一行两个整数 $N, M$，分别表示商店数量和需要购买的饮料瓶数。
接下来 $N$ 行，每行两个整数 $a_i, b_i$，表示第 $i$ 家商店的单价和最大购买数量。

输出格式

一行一个整数，表示买恰好 $M$ 瓶饮料的最小总花费。

样例

2 5
2 4
3 10

11

样例解释

最优方案：先从单价 $2$ 的商店买 $4$ 瓶（花费 $8$），再从单价 $3$ 的商店买 $1$ 瓶（花费 $3$），总花费 $8+3=11$。

数据范围

• $1\le N\le 2\times 10^5$
• $0\le M\le 10^{12}$
• $1\le a_i\le 10^9$
• $0\le b_i\le 10^{12}$

数据保证 $\sum b_i \ge M$