Playlist

题意翻译

你有一个有 $n$ 首歌曲的播放列表，第 $i$ 首歌有 $t_i$ 和 $b_i$ 两个特征——分别是它的长度和好听程度。 听这些歌的快乐程度等于这些歌的总长度乘他们中的最小的好听程度。举个例子，听三首长度为 $[5, 7, 4]$ 而好听程度为 $[11, 14, 6]$ 的歌曲获得的快乐程度等于 $(5 + 7 + 4) \times 6 = 96$。 你需要从你的播放列表中选出最多 $k$ 首歌，使听这些歌的快乐程度尽可能的大。 **【输入格式】** 第一行输入 $n$ 和 $k$（$1 \le k \le n \le 3 \times {10}^5$）两个整数——分别是播放列表中歌的数量和你最多选的歌的数量。 下面的 $n$ 行，每行包含两个整数 $t_i$ 和 $b_i$（$1 \le t_i, b_i \le {10}^6$）——第 $i$ 首歌的长度和好听程度。 **【输出格式】** 输出一个整数——最大的可能快乐程度。

题目描述

You have a playlist consisting of $ n $ songs. The $ i $ -th song is characterized by two numbers $ t_i $ and $ b_i $ — its length and beauty respectively. The pleasure of listening to set of songs is equal to the total length of the songs in the set multiplied by the minimum beauty among them. For example, the pleasure of listening to a set of $ 3 $ songs having lengths $ [5, 7, 4] $ and beauty values $ [11, 14, 6] $ is equal to $ (5 + 7 + 4) \cdot 6 = 96 $ . You need to choose at most $ k $ songs from your playlist, so the pleasure of listening to the set of these songs them is maximum possible.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 3 \cdot 10^5 $ ) – the number of songs in the playlist and the maximum number of songs you can choose, respectively. Each of the next $ n $ lines contains two integers $ t_i $ and $ b_i $ ( $ 1 \le t_i, b_i \le 10^6 $ ) — the length and beauty of $ i $ -th song.

输出格式

Print one integer — the maximum pleasure you can get.

输入输出样例

输入样例 #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

说明

In the first test case we can choose songs $ {1, 3, 4} $ , so the total pleasure is $ (4 + 3 + 6) \cdot 6 = 78 $ . In the second test case we can choose song $ 3 $ . The total pleasure will be equal to $ 100 \cdot 100 = 10000 $ .