题目描述

在你的网抑云音乐里有一个歌单，歌单中有 $n$ 首歌。其中第 $i$ 首歌用两个整数表示 —— $t_i$ 和 $b_i$，分别表示第 $i$ 首歌的长度以及优美度。

当你从歌单中选择一些歌曲来听，你的享受程度等于你所选择这些歌曲的长度之和乘以这些歌曲的优美度的最小值。举个例子，如果你选择了 $3$ 首歌，这 $3$ 首歌的长度为 $[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$），表示每首歌的长度以及优美度。

输出格式

输出一个整数，表示在选择不超过 $k$ 首歌的情况下能够获得的最大的享受程度。

4 3
4 7
15 1
3 6
6 8

78

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

10000

说明/提示

样例解释

样例1：选择第 $1, 3, 4$ 首歌，最大享受程度为 $(4 + 3 + 6) \cdot 6 = 78$

样例2：值选择第 $3$ 首歌，最大享受程度为 $100 \cdot 100 = 10000$

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 30, t_i, b_i \le 100$
• 对于 $60\%$ 的数据，$n \le 3 \cdot 10^3, t_i, b_i \le 10^4$
• 对于 $100\%$ 的数据，$1 \le k \le n \le 3 \cdot 10^5, 1 \le t_i, b_i \le 10^6$