题目描述

你有一个有 $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$ 首歌的长度和好听程度。

输出格式

输出一个整数——最大的可能快乐程度。

4 3
4 7
15 1
3 6
6 8

78

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

10000