← 返回题目列表

AtCoder · abc121_c

C. 能量饮料收藏家

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

听说能量饮料在这些网站上的评分提高,高桥决定购买 M 罐装能量饮料。

有 N 销售能量饮料的商店。在 i第第商店,他最多可以购买 B_i 罐装能量饮料 A_i 日元(日本货币)各一个。

他可以购买的最低金额是多少 M 罐装能量饮料?

保证在给定的投入下,总能买到足够多的钱 M 罐装能量饮料。

约束

  • 输入中的所有值都是整数。
  • 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

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

输出

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


示例输入 1

2 5
4 9
2 4

示例输出 1

12

与 12 日元,我们可以在第一家商店购买一杯饮料,在第二家商店购买四杯饮料,总共五杯饮料。然而我们买不到 5 饮料 11 日元或更少。


示例输入 2

4 30
6 18
2 5
3 10
7 9

示例输出 2

130

示例输入 3

1 100000
1000000000 100000

示例输出 3

100000000000000

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