Description

小J家有N个面包，每个面包都有其种类及基本美味值。

小J希望选出K个面包并且满意值最大

满意值分成两部分

1：对选中的面包的基本美味值进行累加

2：奇异值：设K个面包有T种，则奇异值为T*T

Format

Input

第一行给出N，K

接下来N行，每行给出面包的种类及基本美味值

1<=K<=N<=1e5

美味值<=1e9

Output

如题

Samples

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

26

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

25

7 6
2 7
5 8
4 5
2 3
3 4
4 7
3 5

52

Hint

样例解释 1

吃第 1,2,3 个时，“基础美味程度总和” 为 9+7+6=22，“奇异值” 为2×2=4 ，得到 “满足感” 最大值为 26 ，可以验证不存在更好的吃法。

样例解释 2

吃第1,2,3,4 个，可以发现存在更好的吃法。