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

  val Array(n, k) = readLine.trim.split(' ').map(_.toInt)
  val books = Array.fill(10){Nil: List[Int]}
  for (_ ← 0 until n) {
    val Array(c, g) = readLine.trim.split(' ').map(_.toInt)
    books(g - 1) ::= c
  }
  for (i ← books.indices) books(i) = books(i).sorted(Ordering.Int.reverse)
  val bonus = books.map{_.size}
  val maxPrice = Array.fill(k + 1){0L}
  for (g ← books.indices) {
    for (i ← maxPrice.indices.reverse) {
      var t = 1
      var sum = 0
      for (p ← books(g) if i + t < maxPrice.length) {
        sum += p
        if (maxPrice(i + t) < maxPrice(i) + sum + (t - 1) * t) {
          maxPrice(i + t) = maxPrice(i) + sum + (t - 1) * t
        }
        t += 1
      }
    }
  }
  println(maxPrice.max)
}
