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: # 種類が同じ寿司であれば、最も美味しさが高い寿司を選ぶべき。
  # 従い、
  # (1)各種類の最も美味しさが高い寿司グループ
  # (2)それ以外の寿司グループ
  # をいずれも降順に並べて、(1)から幾つ取るか(最低でも1つは取る)を全探索する
  import sys
  
  readline = sys.stdin.readline
  
  N, K = map(int, readline().split())
  
  from collections import defaultdict
  
  sushi = defaultdict(list)  # 種類・おいしさ　のdictionary
  
  for i in range(N):
      t, d = map(int, readline().split())
      sushi[t].append(d)
  
  best_sushi = []
  other_sushi = []
  
  for value in sushi.values():
      value = sorted(value, reverse=True)
      best_sushi.append(value[0])
      other_sushi += value[1:]
  
  best_sushi = sorted(best_sushi, reverse=True)
  other_sushi = sorted(other_sushi, reverse=True)
  
  # print("best_sushi",best_sushi)
  # print("other_sushi",other_sushi)
  
  best_num = 1  # best_sushiから選ぶ個数
  other_num = K - 1  # other_sushiから選ぶ個数
  
  if len(other_sushi) < other_num:  # 選べない場合
      other_num = len(other_sushi)
      best_num = K - other_num
  
  # それぞれの寿司から選ぶ個数の開始値が決定
  # other_sushiの後ろの要素は切り離して良い
  
  other_sushi = other_sushi[:other_num]
  
  sushi_point = sum(best_sushi[:best_num]) + sum(other_sushi)
  kind_point = best_num**2
  
  ans = sushi_point + kind_point
  # print("初期値",ans,"sum(best_sushi[:best_num])",sum(best_sushi[:best_num]),"sum(other_sushi)",sum(other_sushi),"best_num ** 2",best_num ** 2)
  
  # best寿司のインデックスを進めていく
  for i in range(best_num, len(best_sushi)):
      sushi_point += best_sushi[i]
      # print("----best_sushi[i]",best_sushi[i],"を追加")
      if len(other_sushi) == 0:
          break
      rem = other_sushi.pop()  # 取り除く寿司
      sushi_point -= rem
      kind_point = (i + 1) ** 2
  
      # print("sushi_point",sushi_point,"kind_point",kind_point,"合計",sushi_point + kind_point)
  
      if ans < sushi_point + kind_point:
          ans = sushi_point + kind_point
  
  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."}]