#abc116d. [abc116_d]Various Sushi

[abc116_d]Various Sushi

Problem Statement

There are NN pieces of sushi. Each piece has two parameters: "kind of topping" tit_i and "deliciousness" did_i. You are choosing KK among these NN pieces to eat. Your "satisfaction" here will be calculated as follows:

  • The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".
  • The base total deliciousness is the sum of the deliciousness of the pieces you eat.
  • The variety bonus is x\*xx\*x, where xx is the number of different kinds of toppings of the pieces you eat.

You want to have as much satisfaction as possible. Find this maximum satisfaction.

Constraints

  • 1leqKleqNleq1051 \\leq K \\leq N \\leq 10^5
  • 1leqtileqN1 \\leq t_i \\leq N
  • 1leqdileq1091 \\leq d_i \\leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN KK t1t_1 d1d_1 t2t_2 d2d_2 .. .. .. tNt_N dNd_N

Output

Print the maximum satisfaction that you can obtain.


Sample Input 1

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

Sample Output 1

26

If you eat Sushi 1,21,2 and 33:

  • The base total deliciousness is 9+7+6=229+7+6=22.
  • The variety bonus is 2\*2=42\*2=4.

Thus, your satisfaction will be 2626, which is optimal.


Sample Input 2

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

Sample Output 2

25

It is optimal to eat Sushi 1,2,31,2,3 and 44.


Sample Input 3

6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

Sample Output 3

4900000016

Note that the output may not fit into a 3232-bit integer type.