各种寿司

题目描述

有 $N$ 个寿司,每个寿司都设定了「配料」$t_i$ 和「美味度」$d_i$ 两个参数。 你打算从这 $N$ 个寿司中选出 $K$ 个来吃。 此时的「满足度」按如下方式计算:

• 「满足度」是「美味基础分」与「种类加成」之和。
• 「美味基础分」是所吃寿司的「美味度」之和。
• 「种类加成」是:设所吃寿司的「配料」种类数为 $x$,则加成为 $x*x$。

你想让「满足度」尽可能大。 请计算此时的「满足度」的值。

输入格式

输入按以下格式从标准输入给出:

$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$ 位整数范围。

数据范围

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