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

喝咖啡会给你的大脑带来恢复值, 恢复值是"美味程度总和"和"多种类加成"相加得到.

• "美味程度总和" $x$ 是指所喝咖啡的美味程度相加得到
• "多种类加成"是指不同咖啡类型数量的平方, 比如你喝了 $y$ 个不同类型的咖啡, 则为 $y^2$ .
• 恢复值 $=x + y^2$

现在辰辰想喝 $m$ 杯咖啡, 使得恢复值最大.

数据格式

输入格式

第一行两个整数 $n, m$ .

接下来 $n$ 行, 每行两个整数 $t_i$ 和 $d_i$ .

输出格式

输出一个整数表示喝$m$杯咖啡的最大恢复值.

样例

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

26

样例1解释

选择第 $1, 3, 5$ 杯咖啡, 则$x = 6 + 9 + 7, y = 2^2$ , 恢复值 $=26$

7 4
1 10
1 9
1 8
1 7
2 6
3 5
4 4

41

数据范围

$1<= m <= n<= 10^5$

$1 <= t_i <= n$

$1 <= d_i <= 10^9$