let () = Scanf.scanf "%d %d\n" @@ fun n k ->
  let tds = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun t d -> t - 1, d in
  Array.sort (fun (_, d) (_, d') -> compare d' d) tds;
  let q = Queue.create () in
  let s = Stack.create () in
  let sum = ref 0 in
  let kind = ref 0 in
  let card = Hashtbl.create n in
  for i = 0 to k - 1 do
    sum := !sum + snd tds.(i);
    Hashtbl.replace card (fst tds.(i))
      (1 + try Hashtbl.find card (fst tds.(i)) with Not_found -> 0);
    if Hashtbl.find card (fst tds.(i)) = 1
    then incr kind
    else Stack.push (snd tds.(i)) s
  done;
  for i = k to n - 1 do
    Hashtbl.replace card (fst tds.(i))
      (1 + try Hashtbl.find card (fst tds.(i)) with Not_found -> 0);
    if Hashtbl.find card (fst tds.(i)) = 1 then Queue.push (snd tds.(i)) q
  done;
  let sat = ref (!sum + !kind * !kind) in
  while not (Stack.is_empty s) && not (Queue.is_empty q) do
    sum := !sum + Queue.pop q - Stack.pop s;
    incr kind;
    sat := max !sat (!sum + !kind * !kind)
  done;
  Printf.printf "%d\n" !sat
