### constant

MAXGE = 10

### main

n, k = gets.strip.split(' ').map{|s| s.to_i}

books = MAXGE.times.map{[]}
nge = 0

n.times do
  ci, gi = gets.strip.split(' ').map{|s| s.to_i}
  books[gi - 1] << ci
  nge = gi if nge < gi
end

for g in (0...nge)
  books[g].sort!{|a, b| b <=> a}
end
#p nge
#p books

costs = [0]

for g in (0...nge)
  bs = books[g]
  bslen = bs.length

  costs0 = costs.clone
  clen = costs.length

  csum = 0

  for nbk in (0...bslen)
    csum += bs[nbk]
    csum0 = csum + nbk * (nbk + 1)

    for i in (0...clen)
      j = i + nbk + 1
      break if j > k
      nc = costs[i] + csum0
      if costs0[j].nil? || costs0[j] < nc
        costs0[j] = nc
      end
    end
  end

  costs = costs0
  #p [g, costs]
end

puts costs[k]