Reference: AtCoder ABC116 D — Various Sushi

There are ~N~ pieces of sushi. Sushi ~i~ has:

• a topping type ~t_i~;
• a deliciousness value ~d_i~.

You must select exactly ~K~ pieces.

Let:

• ~S~ be the sum of the deliciousness values of the selected pieces;
• ~x~ be the number of distinct topping types among the selected pieces.

Your total satisfaction is:

~S + x^2~

Find the maximum satisfaction that can be obtained.

Input

• The first line contains two integers ~N~ and ~K~.
• The following ~N~ lines each contain two integers: ~t_i~ and ~d_i~.

Output

• Print one integer: the maximum possible satisfaction.

Constraints

• ~1 \le K \le N \le 10^5~
• ~1 \le t_i \le N~
• ~1 \le d_i \le 10^9~

Example 1

Input:

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

Output:

26