题目描述

There are $N$ pieces of sushi. Each piece has two parameters: "kind of topping" $t_i$ and "deliciousness" $d_i$. You are choosing $K$ among these $N$ pieces to eat. Your "satisfaction" here will be calculated as follows:

• The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".
• The base total deliciousness is the sum of the deliciousness of the pieces you eat.
• The variety bonus is $x*x$, where $x$ is the number of different kinds of toppings of the pieces you eat.

You want to have as much satisfaction as possible. Find this maximum satisfaction.

有 $N$ 块寿司。每块寿司有两个参数："配料种类" $t_i$ 和 "美味程度" $d_i$ 。您要从这些 $N$ 块寿司中选择 $K$ 块食用。您的 "满意度 "计算如下

• 满意度是 "基本总美味 "和 "品种奖励 "的总和。
• 基本总美味度 "是您所吃的每块食物的美味度总和。
• 品种奖励为 $x*x$ ，其中 $x$ 是您所吃的配料的种类数。

您希望获得尽可能多的满足感。找出最大满足感。

输入格式

输入内容按以下格式标准输入：

$N$ $K$
$t_1$ $d_1$
$t_2$ $d_2$
$.$
$.$
$.$
$t_N$ $d_N$

输出格式

打印您能获得的最大满意度。

样例 #1

样例输入 #1

5 3
1 9
1 7
2 6
2 5
3 1

样例输出 #1

26

样例 #2

样例输入 #2

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

样例输出 #2

25

样例 #3

样例输入 #3

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

样例输出 #3

4900000016

说明

数据规模与约定

• $1 \leq K \leq N \leq 10^5$
• $1 \leq t_i \leq N$
• $1 \leq d_i \leq 10^9$
• 输入值均为整数。

样例 $1$ 解释

如果你吃了寿司 $1,2$ 和 $3$ ：

• 基本美味总量为 $9+7+6=22$ 。
• 品种奖励为 $2*2=4$ 。

因此，您的满意度为 $26$ ，这是最佳值。

样例 $2$ 解释

吃寿司 $1,2,3$ 和 $4$ 最佳。

样例 $3$ 解释

注意，输出可能不适合 $32$ （位）整数类型。