题目描述

有 $N$ 片寿司，每片寿司有两个参数："配料种类" $t_i$ 和 "美味程度" $d_i$。你要从这些 $N$ 片中选择 $K$ 片来吃。你的 "满意度" 将根据以下公式计算：

• 满意度等于 "基础总美味程度" 和 "品种奖励" 的和。
• 基础总美味程度等于你吃掉的寿司的美味程度之和。
• 品种奖励为 $x\*x$，其中 $x$ 是你吃掉的寿司的不同配料种类的数量。

你希望获得尽可能多的满意度。找到最大的满意度值。

约束条件

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

输入

从标准输入读取数据，具体格式如下：

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

输出

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

示例输入 1

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

示例输出 1

26

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

• 基础总美味程度为 $9+7+6=22$。
• 品种奖励为 $2\*2=4$。

因此，你的满意度将为 $26$，这是最优解。

示例输入 2

7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

示例输出 2

25

最优解是吃掉寿司 $1,2,3$ 和 $4$。

示例输入 3

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

示例输出 3

4900000016

请注意，输出结果可能无法适应 $32$ 位整数类型。