You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $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 位整数类型。