object Main extends App {
  import scala.io.StdIn._

  implicit class StreamExt[T](st: Stream[T]) {
    def takeThrough(f: T => Boolean): Stream[T] =
      st.takeWhile(f) ++ (st.dropWhile(f).head #:: Stream.empty[T])
  }

  implicit class SeqExt[T](seq: Seq[T]) {
    def dropFirst(t: T): Seq[T] = seq match {
      case head +: tail if head == t => tail
      case head +: tail              => head +: tail.dropFirst(t)
      case _                         => Nil
    }
  }

  case class Sushi(kind: Long, point: Long)

  def search(baseList: Seq[Sushi], rest: Seq[Sushi]): (Seq[Sushi], Seq[Sushi]) = {
    baseList
      .groupBy(_.kind)
      .values
      .flatMap { seq =>
        if (seq.size <= 1) Seq.empty
        else seq
      }
      .toSeq
      .sortBy(_.point)
      .headOption
      .map { minSushi =>
        rest.filter(r => !baseList.map(_.kind).contains(r.kind)) match {
          case newSushi +: nextRest => (newSushi +: baseList.dropFirst(minSushi), nextRest)
          case _                    => (baseList, Nil)
        }
      }
      .getOrElse((baseList, Nil))
  }

  val n +: k +: _ = readLine().split(" ").map(_.toInt).toSeq
  val list: Seq[Sushi] = Stream
    .continually(readLine())
    .take(n)
    .map(_.split(" ").map(_.toInt).toSeq)
    .map {
      case k +: p +: _ => Sushi(k, p)
    }
    .toList
    .sortBy(_.point)(Ordering[Long].reverse)

  println(
    Stream
      .iterate((list.take(k), list.drop(k)))(t => search(t._1, t._2))
      .takeThrough(_._2.nonEmpty)
      .map(_._1)
      .map(seq => seq.map(_.point).sum + Math.pow(seq.map(_.kind).distinct.size, 2).toLong)
      .max
  )
}
