output_description: Print the maximum satisfaction that you can obtain.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      t_1 d_1
      t_2 d_2
      .
      .
      .
      t_N d_N
attempt: # 解説見て書く
  
  N, K = [int(x) for x in input().split()]
  td = [0] * (N)
  for i in range(N):
      td[i] = [int(x) for x in input().split()]
  
  # ネタ種類降順でソート
  # 同じネタの中ではおいしいものから順に並ぶ
  td = sorted(td, reverse=True)
  
  var_p1 = [0] * N  # 種類数を増やす寿司のリスト
  var_p0 = [0] * N  # 種類数を増やさない寿司のリスト
  
  n_p1 = 0
  n_p0 = 0
  for i in range(N):
      if i == 0 or (i > 0 and td[i][0] != td[i - 1][0]):  # 種類が変わる
          var_p1[n_p1] = td[i][1]  # おいしさを追加
          n_p1 += 1
      else:
          var_p0[n_p0] = td[i][1]  # おいしさを追加
          n_p0 += 1
  
  var_p1.sort(reverse=True)
  var_p0.sort(reverse=True)
  
  val_taste = sum(var_p0[0:K])
  val_vars = 0
  ans = 0
  
  for j in range(1, K + 1):  # 種類数1〜Kを試す
      val = var_p1[j - 1]
      if val <= 0:
          break  # これ以上種類を増やせない
      # var_p1からn_p1個選び、var_p0からK - n_p1個選ぶ
      val_taste = val_taste + val - var_p0[K - j]
      val_vars = j * j
      ans = max(ans, val_taste + val_vars)
  
  print(ans)
  
problem_description: 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.
samples: [{"input": "5 3\n    1 9\n    1 7\n    2 6\n    2 5\n    3 1", "output": "26\n    \n\nIf you eat Sushi 1,2 and 3:\n\n  * The base total deliciousness is 9+7+6=22.\n  * The variety bonus is 2*2=4.\n\nThus, your satisfaction will be 26, which is optimal.\n\n* * *"}, {"input": "7 4\n    1 1\n    2 1\n    3 1\n    4 6\n    4 5\n    4 5\n    4 5", "output": "25\n    \n\nIt is optimal to eat Sushi 1,2,3 and 4.\n\n* * *"}, {"input": "6 5\n    5 1000000000\n    2 990000000\n    3 980000000\n    6 970000000\n    6 960000000\n    4 950000000", "output": "4900000016\n    \n\nNote that the output may not fit into a 32-bit integer type."}]