import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.PriorityQueue

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N, K = in.next().toInt
  val t = new Array[Int](N+1)
  val d = new Array[Long](N+1)
  for (i <- 1 to N) {
    t(i) = in.next().toInt
    d(i) = in.next().toLong
  }


  //
  val sushi = Array.fill[List[Int]](N+1)(Nil)
  for (i <- 1 to N) {
    sushi(t(i)) = i :: sushi(t(i))
  }

  var ans = 0L
  val kinds = new Array[Int](N+1)
  var kind = 0L
  var lst: List[(Long, Int)] = Nil // (score, index)
  for (i <- 1 to N) {
    if (!sushi(i).isEmpty) {
      val (v, k) = sushi(i).map(x => (d(x), x)).max
      sushi(i) = sushi(i).filter(_ != k)

      kinds(i) += 1
      kind += 1
      ans += v
      
      lst = (v, k) :: lst
    }
  }

  val pq = new PriorityQueue[(Long, Int)]
  for (i <- 1 to N) {
    if (!sushi(i).isEmpty) {
      for (e <- sushi(i)) {
        pq.enqueue((d(e), e))
      }
    }
  }


  if (lst.length > K) {
    lst = lst.sorted.reverse
    for ((v, k) <- lst.drop(K))
      kinds(t(k)) = 0

    lst = lst.take(K)
    ans = lst.map(_._1).sum
    kind = K
  }
  else if (lst.length < K) {
    for (_ <- 1 to K - lst.length) {
      val (v, k) = pq.dequeue()
      ans += v
      kinds(t(k)) += 1
      lst = (v, k) :: lst
    }
  }


  var ans2 = ans + kind * kind

  val pq2 = new PriorityQueue[(Long, Int)]
  for ((v, k) <- lst) {
    pq2.enqueue((-v, k))
  }

  while (!pq.isEmpty) {
    val (v1, k1) = pq.dequeue()
    val (_v2, k2) = pq2.dequeue()
    val v2 = -_v2

    if (v1 > v2) {
      pq2.enqueue((-v1, k1))

      kinds(t(k2)) -= 1
      if(kinds(t(k2)) == 0)
        kind -= 1

      if(kinds(t(k1)) == 0)
        kind += 1
      kinds(t(k1)) += 1

      ans += v1 - v2
      ans2 = Math.max(ans2, ans + kind * kind)
    }
    else {
      pq2.enqueue((-v2, k2))
    }

  }

  println(ans2)
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}
