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: package main
  
  import (
      "bufio"
      "os"
      "strings"
      "strconv"
      "fmt"
      "sort"
      "container/heap"
      "math"
  )
  
  var sc = bufio.NewScanner(os.Stdin)
  
  func readLineToInt() []int {
      sc.Scan()
      line := strings.Split(sc.Text(), " ")
      var intLine []int
      for _, str := range line {
          n, _ := strconv.Atoi(str)
          intLine = append(intLine, n)
      }
      return intLine
  }
  
  
  /****************** Pair ********************/
  type Pair struct {
      a int
      b int
  }
  
  type SortablePairs struct {
      arr []*Pair
      lessfunc []lessFunc
  }
  
  type lessFunc func(i, j *Pair) bool
  
  func (sp SortablePairs) Len() int {
      return len(sp.arr)
  }
  
  func (sp SortablePairs) Swap(i, j int) {
      sp.arr[i], sp.arr[j] = sp.arr[j], sp.arr[i]
  }
  
  func (sp SortablePairs) Less(i, j int) bool {
      p, q := sp.arr[i], sp.arr[j]
      for k := 0; k < len(sp.lessfunc); k++ {
          less := sp.lessfunc[k]
          if less(p, q) {
              return true
          } else if less(q, p) {
              return false
          }
      }
      return false
  }
  
  /***************** HeapQue *****************/
  
  type PriorityQueue struct {
      arr []*Pair
      size int
  }
  /** sort **/
  func (pq PriorityQueue) Len() int {
      return len(pq.arr)
  }
  
  func (pq PriorityQueue) Swap(i, j int) {
      pq.arr[i], pq.arr[j] = pq.arr[j], pq.arr[i]
  }
  
  func (pq PriorityQueue) Less(i, j int) bool{
      return pq.arr[i].a < pq.arr[j].a
  }
  
  /**** pq ****/
  func (pq *PriorityQueue) Push(x interface{}) {
      item := x.(*Pair)
      pq.arr = append(pq.arr, item)
      pq.size++
  }
  
  func (pq *PriorityQueue) Pop() interface{} {
      n := pq.size
      item := pq.arr[n - 1]
      pq.arr = pq.arr[:n - 1]
      pq.size--
      return item
  }
  
  func max(a, b int) int {
      return int(math.Max(float64(a), float64(b)))
  }
  
  func main() {
      nk := readLineToInt()
      n, k := nk[0], nk[1]
      var dic map[int][]int = map[int][]int{}
      var keys []int
      for i := 0; i < n; i++ {
          td := readLineToInt()
          t, d := td[0], td[1]
          _, ok := dic[t]
          if !ok {
              keys = append(keys, t)
          }
          dic[t] = append(dic[t], d)
      }
  
      var sp SortablePairs
      less := func(p, q *Pair) bool {
          return p.a >= q.a
      }
      sp.lessfunc = append(sp.lessfunc, less)
      for _, key := range keys {
          sort.Ints(dic[key])
          length := len(dic[key])
          sp.arr = append(sp.arr, &Pair{dic[key][length - 1], key})
          dic[key] = dic[key][:length - 1]
      }
      sort.Sort(sp)
      var que PriorityQueue
      heap.Init(&que)
      queScore := 0
      defaultScore := 0
      cnt := 0
      ans := 0
      for _, p := range sp.arr {
          defaultScore += p.a + cnt * 2 + 1
          cnt++
          if cnt >= k {
              ans = max(ans, defaultScore)
              break
          }
          for _, add := range dic[p.b] {
              heap.Push(&que, &Pair{add, p.b})
              queScore += add
          }
          for que.size > k - cnt {
              item := heap.Pop(&que).(*Pair)
              queScore -= item.a
          }
          ans = max(ans, defaultScore + queScore)
      }
      fmt.Println(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."}]