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: import collections
  
  
  class Sushi(object):
      def __init__(self, lines):
          neta, oishisa = map(int, lines.split())
          self.neta = neta
          self.oishisa = oishisa
  
      def __str__(self):
          return "寿司:{0} 美味しさ:{1}".format(self.neta, self.oishisa)
  
  
  def score_out(eat_list):
      score = 0
      items = list(collections.Counter([i.neta for i in eat_list]).items())
      score += len(items) ** 2
      basic_points = [i.oishisa for i in eat_list]
      score += sum(basic_points)
  
      return score
  
  
  N, K = map(int, input().split())
  
  sushi_list = [Sushi(input()) for _ in range(N)]
  
  sushi_list = sorted(sushi_list, key=lambda x: x.oishisa)
  
  eat_list = []
  
  neta_max = len(list(collections.Counter([i.neta for i in sushi_list]).items()))
  
  
  for i in range(K):
      eat_list.append(sushi_list.pop())
      # print(eat_list[i])
  
  eat_items = list(collections.Counter([i.neta for i in eat_list]).items())
  
  if len(eat_items) == K:
      print(score_out(eat_list))
      exit(0)
  
  low_band_types = len(eat_items)
  
  maxscore = score_out(eat_list)
  for i in range(N):
      # 寿司が全て独立しているか判断する。
      # 独立してたら終了させる。
      # 寿司屋のネタの最大種類==選択したネタが最大種類でも終了
      eat_list = sorted(eat_list, key=lambda x: x.oishisa)
      # print ( '現在の寿司' )
      for i in eat_list:
          # print(i)
          pass
      # print('\n')
  
      if len(
          list(collections.Counter([i.neta for i in eat_list]).items())
      ) == K and maxscore <= score_out(eat_list):
          print(score_out(eat_list))
          exit(0)
      elif len(
          list(collections.Counter([i.neta for i in eat_list]).items())
      ) == neta_max and maxscore <= score_out(eat_list):
          print(score_out(eat_list))
          exit(0)
  
      eat_items = list(collections.Counter([i.neta for i in eat_list]).items())
      neta_kaburi_list = [i[0] for i in eat_items if i[1] > 1]
      # print(neta_kaburi_list)
      min_oishisa = -1
      kick_avails = []
      for kaburi_neta in neta_kaburi_list:
          kick_avails += [i for i in eat_list if i.neta == kaburi_neta]
      kick_avails = sorted(kick_avails, key=lambda x: x.oishisa, reverse=True)
      if not kick_avails:
          print(maxscore)
          exit(0)
      kick = kick_avails.pop()
      # print('kick as')
      # print(kick)
      eat_list.remove(kick)
      sushi_list = sorted(sushi_list, key=lambda x: x.oishisa)
      ef = True
      neta_list = [i[0] for i in eat_items]
  
      if not sushi_list:
          print(maxscore)
          exit(0)
  
      while ef:
          eat_list = sorted(eat_list, key=lambda x: x.oishisa, reverse=True)
          sushi = sushi_list.pop()
          # print('poped sushi is ')
          # print(sushi)
          if sushi.neta in neta_list:
              pass
          else:
  
              eat_list.append(sushi)
              ef = False
  
      if score_out(eat_list) > maxscore:
          maxscore = score_out(eat_list)
  
  print(maxscore)
  
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."}]