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: def main():
      N, K = list(map(int, input().split()))
      sushi_list = list()
      for _ in range(N):
          t, d = list(map(int, input().split()))
          t -= 1
          sushi_list.append((t, d))
      sushi_list.sort(key=lambda s: s[1], reverse=True)  # おいしさの降順でソート
      # おいしさTop Kのすしをとるのを初期解とする
      neta_flag_list = [0] * N
      topk_extra_sushi_list = list()  # Top Kのすしで、各ネタ最大のおいしさはないすし
      additional_sushi_list = (
          list()
      )  # Top Kのすしのネタ以外で、各ネタの最大のおいしさのすし
      point_topk = 0
      for k, sushi in enumerate(sushi_list):
          if k < K:
              if neta_flag_list[sushi[0]] == 1:
                  topk_extra_sushi_list.append(sushi)
              point_topk += sushi[1]
          else:
              if neta_flag_list[sushi[0]] == 0:
                  additional_sushi_list.append(sushi)
          neta_flag_list[sushi[0]] = 1
      n_neta = K - len(topk_extra_sushi_list)
      point_topk += n_neta**2
      # その他のネタをt種類追加する場合を考えて、初期解と比較していく
      d_extra, d_additional = 0, 0
      ans = point_topk
      n_additional_neta = min(
          K - n_neta, len(topk_extra_sushi_list), len(additional_sushi_list)
      )
      for t in range(1, n_additional_neta + 1):
          n_cur_neta = n_neta + t
          d_extra += topk_extra_sushi_list[-t][1]
          d_additional += additional_sushi_list[t - 1][1]
          point = point_topk - d_extra + d_additional + (n_cur_neta**2 - n_neta**2)
          ans = max(ans, point)
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
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."}]