AT_abc121_c [ABC121C] Energy Drink Collector

题目描述

听说营养饮料有提升评级的效果，高桥君决定要买 $M$ 瓶营养饮料。

有 $N$ 家店铺在售卖营养饮料，第 $i$ 家店铺每瓶营养饮料售价 $A_i$ 日元，最多可以买 $B_i$ 瓶。

请问，至少需要多少钱才能买到 $M$ 瓶营养饮料？

另外，保证在给定的输入下，如果有足够的钱，一定可以买到 $M$ 瓶营养饮料。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

输出买到 $M$ 瓶营养饮料所需的最小金额。

样例 1

输入

2 5
4 9
2 4

输出

12

样例 2

输入

4 30
6 18
2 5
3 10
7 9

输出

130

样例 3

输入

1 100000
1000000000 100000

输出

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_2 + \cdots + B_N \geq M$

样例解释 1

只需 $12$ 日元即可在第 $1$ 家店买 $1$ 瓶，在第 $2$ 家店买 $4$ 瓶，总共买到 $5$ 瓶营养饮料。而如果只有 $11$ 日元或更少，则无法买到 $5$ 瓶营养饮料。

样例解释 3

输出结果可能超出 $32$ 位整数型的范围。

由 ChatGPT 4.1 翻译