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: # -*- coding: utf-8 -*-
  n, k = map(int, input().split())
  o = {}
  
  for _ in range(n):
      t, d = map(int, input().split())
      if t not in o:
          o[t] = []
      o[t].append(d)
  
  tl = list(o.keys())
  tl.sort(reverse=True, key=lambda x: o[x])
  # print(tl)
  for t in tl:
      o[t].sort(reverse=True)
  # print(o)
  res = -1
  sel = {}
  for t in tl:
      if len(o[t]) <= k:
          sel[t] = len(o[t])
          k -= sel[t]
      else:
          sel[t] = k
          k = 0
      if k == 0:
          break
  
  # print(sel)
  
  
  def calc(sel):
      res = 0
      cnt = 0
      for t in sel:
          if sel[t] > 0:
              cnt += 1
          for i in range(sel[t]):
              res += o[t][i]
      return res + cnt * cnt
  
  
  idx = None
  for i in range(len(tl) - 1):
      if tl[i + 1] not in sel:
          idx = i
          break
  
  if idx is None:
      print(calc(sel))
      exit()
  
  # print(idx)
  
  res = calc(sel)
  for i in range(idx + 1, len(tl)):
      while sel[tl[idx]] == 1:
          idx -= 1
  
      sel[tl[idx]] -= 1
      sel[i] = 1
      # res2 = res + o[i][0] - o[tl[idx]][-1]
      # res = max(res, res2)
      res = max(res, calc(sel))
  
  print(res)
  
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."}]