题目描述

有 $N$ 块寿司。每块寿司有两个参数:“配料种类"$t_i$和“美味程度" $d_i$;。 你需要从这 $N$ 块寿司中选择取$K$ 块来吃。 你在这里的“满足感“将根据以下方式计算:

满足感是“基本总美味程度”和“多样性奖励“的和。

基本总美味程度是你所吃寿司的美味程度之和。

多样性奖励是 $x \times x$，其中$x$是你所吃寿司的不同配料种类的数量。

你希望满足感尽可能大。 求出最大的满足感。

输入

第一行两个整数$N,K$,分别表示寿司的数量和可以选择的寿司数量

接下来$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

提示

$1 \leq K \leq N \leq 10^5$

$1\leq t_i \leq N$

$1 \leq d_i \leq 10^9$

输入中的所有值均为整数

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