You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

辰辰学习(打游戏)学累了, 打算整点快乐肥宅水.

校门口有$n$家商店, 每家商店的单价为$a_i$, 库存为$b_i$.

辰辰打算购买$m$瓶肥宅水分给同学们(队友们).

辰辰最少可以花多少钱?

输入格式

第一行两个整数$n, m$

接下来$n$行, 每行两个整数$a_i, b_i$分别表示单价和库存.

输出格式

输出一个整数表示最少需要花多少钱, 即可购买$m$瓶饮料.

样例 #1

样例输入 #1

2 5
4 9
2 4

样例输出 #1

12

样例 #2

样例输入 #2

4 30
3 10
7 9
6 18
2 5

样例输出 #2

130

提示

数据范围

• $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$