object Main {
  import java.util.Scanner

  def readStrings(n: Int)(implicit sc: Scanner): Array[String] = Array.fill(n) { sc.next() }
  def readInts(n: Int)(implicit sc: Scanner): Array[Int] = Array.fill(n) { sc.nextInt() }
  def readLongs(n: Int)(implicit sc: Scanner): Array[Long] = Array.fill(n) { sc.nextLong() }
  def readLineStrings(implicit sc: Scanner): Array[String] = sc.nextLine().split(' ')
  def readLineInts(implicit sc: Scanner): Array[Int] = readLineStrings.map(_.toInt)
  def readLineLongs(implicit sc: Scanner): Array[Long] = readLineStrings.map(_.toLong)

  def main(args: Array[String]): Unit = solve(new Scanner(System.in))

  def solve(implicit sc: Scanner): Unit = {
    case class Sushi(neta: Int, score: Long)
    val Array(n, k) = readLineInts
    val sushi = Array.fill(n) { val Array(a, b) = readLineInts; Sushi(a, b) }

    val scoreSortedSushi = sushi.sortBy(_.score).reverse
    val topKSushis = scoreSortedSushi.take(k).reverse
    val netaMultiset = scala.collection.mutable.Map(
      topKSushis.map(_.neta).groupBy(identity).mapValues(_.length).toSeq: _*
    )
    val restSorted = scoreSortedSushi.drop(k)

    var totalBaseScore = topKSushis.map(_.score).sum
    var totalNetaNumber = netaMultiset.filter { case(_, s) => s != 0 }.keys.size

    def score = totalBaseScore + (totalNetaNumber * totalNetaNumber)

    var maxTotal = score

    var newSushiSearchLowerBound = 0
    var dropSushiSearchLowerBound = 0
    for { i <- topKSushis.indices } {
      if (netaMultiset(topKSushis(i).neta) >= 2) {
        val firstNewSushiIndex = {
          restSorted
            .drop(newSushiSearchLowerBound)
            .indexWhere(s => !netaMultiset.contains(s.neta))
        }
        val firstDropCandidateIndex = {
          topKSushis
            .drop(dropSushiSearchLowerBound)
            .indexWhere(s => netaMultiset(s.neta) > 1)
        }
        if (firstNewSushiIndex == -1 || firstDropCandidateIndex == -1) return println(maxTotal)

        newSushiSearchLowerBound = firstNewSushiIndex
        dropSushiSearchLowerBound = firstDropCandidateIndex

        val newSushi = restSorted(firstNewSushiIndex)
        val droppedSushi = topKSushis(firstDropCandidateIndex)

        topKSushis(firstDropCandidateIndex) = newSushi
        totalNetaNumber += 1

        netaMultiset(droppedSushi.neta) -= 1
        netaMultiset.+=((newSushi.neta, 1))

        totalBaseScore += newSushi.score - droppedSushi.score

        val newScore = score
        if (newScore > maxTotal) maxTotal = newScore
      }
    }

    println(maxTotal)
  }
}