object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N, K = sc.nextInt()

    case class Sushi(t: Int, d: Long)

    val _Sushis = new Array[Sushi](N)
    (0 until N) foreach { i =>
      val t = sc.nextInt()
      val d = sc.nextLong()
      _Sushis(i) = Sushi(t, d)
    }
    val Sushis = _Sushis.sortBy(_.d)(Ordering.Long.reverse)

    // f(a)とそれを構成するS_aがわかっている時に
    // f(a+1)とそれを構成するS_a+1をを求めることを考えます(x <= a <= N-1)
    // S_a+1はS_aに以下の操作を加えることで構成することができます
    // 1. 集合S_aから、取り除いても「ネタ」の種類数が減らない寿司の中で最も「おいしさ」の小さいものを取り除く
    //    この時点でネタの種類数が減らないものがない場合には, それまでのものから選ぶ
    // 2. 集合S_aに含まれない寿司の中で、集合S_aにない「ネタ」を持つ、最も「おいしさ」の大きいものをS_aに加える
    // この操作を繰り返すことにより、f(i) (x < i <= N)を再帰的に求めることができます。

    val (initialSushis, restSushis) = Sushis.splitAt(K)
    val sushiset = Set(initialSushis.map(_.t): _*)
    var p = sushiset.size.toLong
    val initialV = initialSushis.foldLeft(0L)(_ + _.d) + p * p

    val removableSushis = scala.collection.mutable.PriorityQueue[Sushi]()(Ordering.by[Sushi, Long](_.d).reverse)
    val appendableSushis = scala.collection.mutable.PriorityQueue[Sushi](restSushis.filter(s => !sushiset.contains(s.t)): _*)(Ordering.by[Sushi, Long](_.d))

    {
      val spSushis = initialSushis.sorted(Ordering.by[Sushi, (Int, Long)](s => (s.t, s.d))(Ordering.Tuple2(Ordering.Int, Ordering.Long.reverse)))
      val N = initialSushis.length
      var bef = -1
      var i = 0
      while (i < N) {
        val sushi = spSushis(i)
        if (sushi.t == bef) {
          removableSushis.enqueue(sushi)
        }
        bef = sushi.t
        i += 1
      }
    }

    def solve(bef: Long, max: Long, p: Long): Long =
      if (p < K && removableSushis.nonEmpty && appendableSushis.nonEmpty) {
        val rs = removableSushis.dequeue()
        val as = appendableSushis.dequeue()
        val current = bef - rs.d + as.d + 2 * p + 1
        solve(current, max max current, p + 1)
      } else max

    println(solve(initialV, initialV, p))
  }

}
