n,e = gets.split.map(&:to_i)
su = Array.new(n).map{Array.new(2, 0)}
sushi = Array.new(n+1).map{Array.new(1,0)}
for i in 0..n-1
  su[i] = gets.split.map(&:to_i)
  sushi[su[i][0]].push(su[i][1])
end
count = 0
i = 0
while count <= n
  if sushi[i].length == 1
    sushi.delete_at(i)
  else
    sushi[i].sort!
    sushi[i].delete_at(0)
    i += 1
  end
  count += 1
end
sushi.sort_by! {|s| s[-1]}
eat_s = []
count = 0
base = 0
bonus = 0
for i in 1..sushi.length
  base += sushi[-i][-1]
  bonus += 1
  count += 1
  eat_s.push([i,sushi[-i][-1]])
  if count >= e
    break
  end
end
eat_s2 = []
for i in 1..sushi.length
  if count >= e && i >= eat_s[-1][0]
    break
  end
  if sushi[-i].length > 1
    for j in 2..sushi[-i].length
      check = 0
      if count < e
        count += 1
        eat_s2.push(sushi[-i][-j])
        base += sushi[-i][-j]
        check += 1
      end
      if check == 0 && ((sushi[-i][-j] - eat_s[-1][1]) > (bonus**2 - (bonus-1)**2))
        base += (sushi[-i][-j] - eat_s[-1][1])
        eat_s.delete_at(-1)
        eat_s2.push(sushi[-i][-j])
        bonus -= 1
        count += 1
        check += 1
      end
      if eat_s2.length > 0 && check == 0
        eat_s2.sort!
        if eat_s2[-1] < sushi[-i][-j]
          base += (sushi[-i][-j] - eat_s2[-1])
          eat_s2.delete_at(-1)
          eat_s2.push(sushi[-i][-j])
        end
      end
    end
  end
end
puts base+bonus**2
