← 返回题目列表

Codeforces · 1140/C

C. 播放列表

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

您的播放列表包含 $$$n$$$ 歌曲。第 $$$i$$$ 歌曲的特点是 $$$t_i$$$ 和 $$$b_i$$$ 两个数字——分别是它的长度和美丽。听一组歌曲的乐趣等于该组歌曲的总长度乘以其中的最小美度。例如,聆听一组长度为 $$$[5, 7, 4]$$$ 且美感值为 $$$[11, 14, 6]$$$ 的歌曲的乐趣等于 $$$(5 + 7 + 4) \cdot 6 = 96$$$。

您需要从播放列表中选择最多 $$$k$$$ 首歌曲,这样聆听这些歌曲集的乐趣就最大可能。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) – 分别是播放列表中的歌曲数量和您可以选择的最大歌曲数量。

接下来的 $$$n$$$ 行包含两个整数 $$$t_i$$$ 和 $$$b_i$$$ ($$$1 \le t_i, b_i \le 10^6$$$) — 第 $$$i$$$ 歌曲的长度和美感。

输出

打印一个整数 — 您可以获得的最大乐趣。

示例

输入 #1

4 3
4 7
15 1
3 6
6 8

输出 #1

78

输入 #2

5 3
12 31
112 4
100 100
13 55
55 50

输出 #2

10000

注意

在第一个测试用例中,我们可以选择歌曲$$${1, 3, 4}$$$,所以总的乐趣是$$$(4 + 3 + 6) \cdot 6 = 78$$$。

在第二个测试用例中,我们可以选择歌曲$$$3$$$。总的乐趣将等于 $$$100 \cdot 100 = 10000$$$。