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: class sushi:
    def __init__(self, t, d):
      self.t = t
      self.d = d
  
  list = []
  N, K = map(int, input().split())
  for i in range(N):
    t, d = map(int, input().split())
    list.append(sushi(t, d))
    
  sorted_list = sorted(list, key=lambda sushi:sushi.d, reverse=True)
  
  t_list = []
  rev_list = []
  d_sum = 0
  for i in range(K):
    if t_list.count(list[i].t) == 0:
      t_list.append(list[i].t)
    else:
      rev_list.append(i)
    d_sum += list[i].d
  
  tmp = pow(len(t_list), 2) + d_sum
  
  flag = 0
  while len(rev_list) != 0:
    pointer = rev_list.pop()
    for i in range(K, N, 1):
      if t_list.count(list[i].t) == 0
        l = len(t_list)
        key = pow(l + 1, 2) + list[i].d - pow(l, 2) - list[pointer].d
        if key > 0:
          tmp += key
        else:
          flag = 1
        break
    if flag:
      break
  
  print(tmp)
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."}]