import java.util.*
data class Neta(val t: Int, val d: Int)
fun main(args: Array<String>) {
    val (N, K) = listOfInt()
    val A = Array(N) {
        val (t, d) = listOfInt()
        Neta(t, d)
    }.sortedByDescending { it.d }
    val map = mutableMapOf<Int, Int>()
    val use = PriorityQueue<Neta>(N, Comparator { o1, o2 -> o1.d - o2.d }) //asc
    val rem = PriorityQueue<Neta>(N, Comparator { o1, o2 -> o2.d - o1.d }) //desc
    var sum = 0L
    var ans = 0L
    for (k in 0 until K) {
        use.add(A[k])
        map.put(A[k].t, map.getOrElse(A[k].t, { 0 }) + 1)
        sum += A[k].d
        ans = Math.max(ans, sum + map.size.squaredLong())
    }
    for (k in K until N) rem.add(A[k])
outside@
    while (!use.isEmpty()) {
        val u = use.poll()
if (map.get(u.t)!! >= 2) {
        while (!rem.isEmpty()) {
            val r = rem.poll()
            if (!map.containsKey(r.t)) {
                map.put(r.t, 1)
                sum += r.d - u.d
                ans = Math.max(ans, sum + map.size.squaredLong())
                continue@outside
            }
        }
        break@outside
}
    }
    println(ans)
}
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfLong() = listOfString().map(String::toLong)
fun Int.squaredLong() = this.toLong() * this.toLong()
