N, K = gets.split.map(&:to_i)

sushi = Hash.new { |h, k| h[k] = [] }

N.times do 
  t, d = gets.split.map(&:to_i)

  sushi[t] << d
end

kinds = sushi.keys.size
dp = Array.new(N) { Hash.new(-Float::INFINITY) }
dp[0][0] = 0

ans = 0

sushi.each.with_index do |(s, values), i|
  sum = 0
  rui = []

  values.sort.reverse.each_with_index do |v, idx|
    sum += v
    rui << sum
  end

  ans = rui.last if values.size <= K && ans < rui.last

  i.downto(i) do |k|
    kind_cnt = k + 1

    dp[k].each do |cnt, value|
      rui.each.with_index(1) do |v, c|
        nc = cnt + c

        next if nc > K

        nv = value + v

        if dp[kind_cnt][nc] < nv
          dp[kind_cnt][nc] = nv
        end

        ret = kind_cnt ** 2 + nv

        if ans < ret
          ans = ret
        end
      end
    end
  end
end

puts ans
