D - Various Sushi 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

N 個の寿司があり、それぞれの寿司には「ネタ」t_i と「おいしさ」d_i のパラメータが設定されています。 あなたはこの N 個の寿司の中から K 個を選んで食べようとしています。 この時のあなたの「満足ポイント」は、以下のようにして計算されます。

  • 「満足ポイント」は、「おいしさ基礎ポイント」と、「種類ボーナスポイント」の和である。
  • 「おいしさ基礎ポイント」は、食べた寿司の「おいしさ」の総和である。
  • 「種類ボーナスポイント」は、食べた寿司の「ネタ」の種類数を x としたとき、x*x である。

あなたは、「満足ポイント」をできるだけ大きくしたいです。 この時の「満足ポイント」の値を求めてください。

制約

  • 1 \leqq K \leqq N \leqq 10^5
  • 1 \leqq t_i \leqq N
  • 1 \leqq d_i \leqq 10^9
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

出力

あなたの得られる「満足ポイント」の最大値を出力してください。

入力例 1

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

出力例 1

26

寿司 1,2,3 を食べた時、

  • 「おいしさ基礎ポイント」は、9+7+6=22
  • 「種類ボーナスポイント」は、2*2=4

で、得られる「満足ポイント」は 26 となり、これが最適です。

入力例 2

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

出力例 2

25

寿司 1,2,3,4 を食べるのが最適です。

入力例 3

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

出力例 3

4900000016

出力が 32 bit型整数に収まらない場合もあることに注意して下さい。

Score : 400 points

Problem Statement

There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i. You are choosing K among these N 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*x, where x 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

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

Input

Input is given from Standard Input in the following format:

N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_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,2 and 3:

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

Thus, your satisfaction will be 26, 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,3 and 4.

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 32-bit integer type.