Scanf.scanf "%d %d" (fun n k ->
    let dt = Array.init n (fun _ -> Scanf.scanf " %d %d" (fun t d -> d, t)) in
    Array.sort (fun a b -> compare b a) dt;

    let module S = Set.Make (struct type t = int       let compare = compare end) in
    let module Q = Set.Make (struct type t = int * int let compare = compare end) in

    let iset, iqueue, iscore =
        let rec loop i set queue score =
            if i = k then set, queue, score else
                let (d, t) = dt.(i) in
                if S.mem t set then loop (i + 1) set (Q.add (d, i) queue) (score + d)
                               else loop (i + 1) (S.add t set) queue (score + d)
        in
        loop 0 S.empty Q.empty 0
    in
    let ip = S.cardinal iset in
    let iscore = iscore + ip * ip in
    let rec loop i p qrest queue set curscore maxscore =
        if i = n || qrest = 0 then maxscore else
            let (d, t) = dt.(i) in
            if S.mem t set then loop (i + 1) p qrest queue set curscore maxscore else
                let q = Q.min_elt queue in
                let queue = Q.remove q queue in
                let curscore = curscore - fst q in
                let curscore = curscore + d + 2 * p + 1 in
                loop (i + 1) (p + 1) (qrest - 1) queue (S.add t set) curscore (max maxscore curscore)
    in
    loop k ip (Q.cardinal iqueue) iqueue iset iscore iscore |> Printf.printf "%d\n"
)