D - 各种寿司

得分：$400$ 分

问题描述

有 $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$

输出

输出能够获得的最大满足感。

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

26

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

• 基本总美味程度是 $9+7+6=22$。
• 多样性奖励是 $2*2=4$。

因此，你的满足感将是 $26$，对应最优选择。

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

25

最优选择是吃寿司 $1$、$2$、$3$ 和 $4$。

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

4900000016

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