题目描述

你在家闲来无事，准备听听音乐放松一下。你有一个包含 \(n\) 首歌曲的播放列表，每首歌曲都有两个属性时间长度和优美度，我们记第 \(i\) 首歌曲的长度和优美度为 \(t[i]\) 和 \(b[i]\)。

聆听一组歌曲的乐趣等于该组歌曲的总长度乘以其中的最小优美度。 例如，听一组长度分别为\([5, 7, 4]\)和优美度分别为\([11, 14, 6]\)的3首歌曲的乐趣等于\((5 + 7 + 4) \times 6= 96\)。

你最多可以从播放列表中选择 \(k\) 首(可以不足 \(k\) 首)歌曲进行播放，请计算聆听这些歌曲的最大的乐趣。

格式

输入格式

第一行包含两个整数 \(n\) 和 \(k\)，表示播放列表中的歌曲数和你可以选择进行播放聆听的最大歌曲数。

接下来的 \(n\) 行中的每行包含两个整数 \(t[i]\) 和 \(b[i]\)，表示第 \(i\) 首歌曲的长度和优美度。

输出格式

输出一行包含一个整数，为你可以获得的最大乐趣。

样例1

样例输入1

4 3
4 7
15 1
3 6
6 8

样例输出1

78

样例2

样例输入2

4 3
4 7
15 1
3 6
6 8

样例输出2

78

样例1解释

选择第 \(1,3,4\) 三首歌曲，得到的乐趣为\( (4+3+6)×6=78\)；

样例2解释

仅选择第 \(3\) 首一首歌曲，得到的乐趣为 \(100×100=10000\)。

限制

\(50\%\)的数据：\(1≤ k ≤ n ≤1000\)；

\(100\%\)的数据：\(1≤ k ≤ n ≤3×10^5\)，\(1≤ t[i],b[i] ≤10^6\)。