您的播放列表包含 $$$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$$$。