let rv f p q = f q p
module MultiSet_test = struct
  module Make (X:Map.OrderedType) = struct
    include Map.Make(X)
    let count v set =
      try find v set with Not_found -> 0
    let remove_each v set =
      let k = count v set in
      if k<=0 then raise Not_found
      else if k=1 then remove v set
      else add v (k-1) set
    let add_each v set =
      let k = count v set in
      if k=0 then add v 1 set
      else add v (k+1) set
    let iter_each f set =
      let rec f0 k = function
      | 0 -> ()
      | i -> let () = f k in f0 k (i-1)
      in iter f0 set
    let fold_each f set ac =
      let rec f0 k i ac = match i with
      | 0 -> ac
      | i -> f0 k (i-1) (f k ac)
      in fold f0 set ac
    let bindings_each set =
      fold_each (fun v ls -> v::ls) set []
      |> List.rev
    let min_binding_each set = fst @@ min_binding set
    let max_binding_each set = fst @@ max_binding set
    let exists_each f = exists (fun k _ -> f k)
    let cardinal_each set = (* slow *)
      fold (fun _ v sum -> sum + v) set 0
  end
end
module IRSet = MultiSet_test.Make (struct type t = int let compare = rv compare end);;
Scanf.(Array.(scanf " %d %d" @@ fun n k ->
  let t,d = make n 0,make n 0 in
  let repr = make n 0 in
  init n (fun i -> scanf " %d %d" @@ fun u v ->
    t.(i) <- u-1; d.(i) <- v;
    repr.(t.(i)) <- max v repr.(t.(i))
  ) |> ignore;
  let rest = init n (fun _ -> IRSet.empty) in
  init n (fun i ->
    (* if repr.(t.(i)) <> d.(i) then *)
      rest.(t.(i)) <- IRSet.add_each d.(i) rest.(t.(i))
  ) |> ignore;
  iteri (fun i v ->
    if v>0 then rest.(i) <- IRSet.remove_each v rest.(i)
  ) repr;
  (* iteri (fun i set ->
    Printf.printf "%d: " @@ i+1; IRSet.iter_each (Printf.printf "%2d ") set;
    print_newline ()
  ) rest;
  iteri (fun i v ->
    Printf.printf "%d:%d\n" (i+1) v;
  ) repr; *)
  let repr = to_list repr
  |> List.mapi (fun i v -> v,i)
  |> List.filter (fun (v,i) -> v <> 0)
  |> List.sort (rv compare)
  in
  (* List.iter (fun (v,i) -> Printf.printf "%d:%d; " v @@ i+1) repr; print_newline (); *)
  let _,_,_,res,_ = init n (fun w -> w+1)
  |> fold_left (fun ((best,sum_best,repr,res,car_best) as u) w -> match repr with
    | [] -> u
    | (v,i)::t -> (
      (* Printf.printf "rest.(%d) :: " @@ i+1;
      IRSet.iter_each (Printf.printf "%d ") rest.(i); print_newline (); *)
      let best = IRSet.merge (fun i p q -> match p,q with
      | Some p,Some q -> Some (p+q)
      | Some p,_ | _,Some p -> Some p
      | None,None -> None
      ) best rest.(i) in
      let car_best = car_best + IRSet.cardinal_each rest.(i) in
      (* Printf.printf "car_best=%2d; i=%d\n" car_best @@ i+1; *)
      rest.(i) <- IRSet.empty;
      (* Printf.printf "%d :: " (k-w);
      IRSet.iter_each (Printf.printf "%d ") best; print_newline (); *)
      if k - w < 0 || car_best < k - w then (
        (best,sum_best+v,t,res,car_best)
      ) else
      let u = ref @@ IRSet.empty in
      (* Printf.printf "take: %d\n" (k-w); *)
      let best,sum = init (k-w) (fun i -> i)
      |> fold_left (fun (set,sum) _ ->
        let v = IRSet.min_binding_each set in
        u := IRSet.add_each v !u;
        (IRSet.remove_each v set,sum+v)
        (* (set,sum+v) *)
      ) (best,0)
      in
      let best = IRSet.merge (fun i p q -> match p,q with
      | Some p,Some q -> Some (p+q)
      | Some p,_ | _,Some p -> Some p
      | None,None -> None
      ) best !u in
      (* Printf.printf "  %6d v. %6d :: %2d + %2d + %2d\n"
        res
        (w*w + sum + sum_best + v)
        (w*w)
        sum
        (sum_best + v); *)
      (best,sum_best+v,t,max res (w*w + sum + sum_best + v),car_best)
    )
  ) (IRSet.empty,0,repr,0,0) in
  print_int res
));;
