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: # Greedyを一ひねり
  # 最初はGreedyに取る。それから種類を増やす。2個目以降を削除して、新たなネタの1個目を加える。
  # あるネタの中でポイントが最高かどうかが重要。これを　True　/　False　で管理する
  n, k = list(map(int, input().split()))
  
  sushi = [list(map(int, input().split())) + [None] for _ in range(n)]
  sushi.sort(key=lambda s: s[1], reverse=True)  # 値段の降順
  
  # あるネタの中でポイントが最高なら、 Trueそうでなければ、　False
  neta_seen = set()
  for i in range(n):
      if sushi[i][0] in neta_seen:
          sushi[i][2] = False
      else:
          sushi[i][2] = True
          neta_seen.add(sushi[i][0])
  
  # n_kind = len([s[1] for s in sushi[:k] if s[1] == True ])
  # なんかうまくいかないので、最初からk番目までのTrueの数を愚直に書こう
  
  n_kind = 0
  for i in range(k):
      if sushi[i][2]:
          n_kind += 1
  
  ans = sum([s[1] for s in sushi[:k]]) + n_kind**2
  # print(sushi, ans)
  
  now = ans
  adopt = k
  trash = k - 1
  
  while True:
  
      while adopt < n and sushi[adopt][2] == False:
          adopt += 1
      while trash >= 0 and sushi[trash][2] == True:
          trash -= 1
      if not (adopt < n and trash >= 0):
          break
  
      now = now + sushi[adopt][1] - sushi[trash][1]
      now = now - n_kind**2 + (n_kind + 1) ** 2
  
      # 	print(adopt, trash, now)
  
      n_kind += 1
      adopt += 1
      trash -= 1
  
      if now > ans:
          ans = now
  
  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."}]