#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, K = get_ints
TD = []
N.times do |i|
  TD[i] = [i] + get_ints
end

TD.sort! { |a, b| a[2] <=> b[2] }.reverse!

if K == 1
  puts TD[0][2] + 1
else
  sets = Array.new(N+1) { Set.new }
  kind_bonus = Set.new
  points = 0

  TD[0...K].each.with_index do |(i, t, d)|
    sets[t].add(i)
    kind_bonus.add(t)
    points += d
  end


  max = points + kind_bonus.length ** 2

  left = K-1
  right = K

  while left >= 0
    i, t, d = TD[left]
    # 重複しているものを低い値から探す
    if sets[t].length > 1
      # 重複しているので、これを除いた新しい種類の最大のものを探す
      while right < N
        right_i, right_t, right_d = TD[right]
        unless kind_bonus.include?(right_t)
          points += right_d - d
          kind_bonus.add(right_t)
          sets[t].delete(i)
          sets[right_t].add(right_i)
          stock = points + kind_bonus.length ** 2
          max = stock if stock > max
          break
        end
        right += 1
      end
    end
    left -= 1
  end

  puts max
end

