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: nk = input().split()
  n = int(nk[0])
  k = int(nk[1])
  
  dtlist = []
  for i in range(n):
      td = input().split()
      t = int(td[0])
      d = int(td[1])
      dtlist.append((d, t))
  dtlist.sort(reverse=True)
  
  
  t_to_maxidx = {}
  for idx, dt in enumerate(dtlist):
      d, t = dt
      if t not in t_to_maxidx:
          t_to_maxidx[t] = idx
  
  
  selected = []
  count = 0
  tcount = {}
  
  candidate = [(dtlist[idx][0], idx) for t, idx in t_to_maxidx.items()]
  candidate.sort(reverse=True)
  for d, idx in candidate:
      if count >= k:
          break
      d, t = dtlist[idx]
      selected.append(dtlist[idx])
      count += 1
      tcount[t] = 1 if t not in tcount else tcount[t] + 1
      dtlist[idx] = None
  
  new_dtlist = []
  for dt in dtlist:
      if dt is not None:
          new_dtlist.append(dt)
  dtlist = new_dtlist
  
  
  if k - count > 0:
      for i in range(k - count):
          dt = dtlist.pop(0)
          selected.append(dt)
          d, t = dt
          tcount[t] = 1 if t not in tcount else tcount[t] + 1
  
  selected.sort()
  
  score = 0
  for d, t in selected:
      score += d
  
  len_tcount = len(tcount)
  score += len_tcount * len_tcount
  
  for i in range(0, 2**32):
      next_score = score
      try:
          d_new, t_new = dtlist.pop(0)
          d_old, t_old = selected.pop(0)
      except IndexError:
          print(score)
          break
      next_score += d_new
      next_score -= d_old
  
      tcount[t_old] -= 1
      if tcount[t_old] <= 1:
          next_score -= len_tcount * len_tcount
          len_tcount -= 1
          next_score += len_tcount * len_tcount
          del tcount[t_old]
  
      if t_new not in tcount:
          next_score -= len_tcount * len_tcount
          len_tcount += 1
          next_score += len_tcount * len_tcount
          tcount[t_new] = 1
      else:
          tcount[t_new] += 1
  
      if next_score <= score:
          print(score)
          break
      score = next_score
  
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."}]