Scanf.scanf "%d %d" (fun n m ->
    let a = Array.init n (fun _ -> Scanf.scanf " %d" (fun a -> a)) in
    Array.sort (fun a b -> compare b a) a;
    let b = Array.make n 0 in
    b.(0) <- a.(0);
    for i = 1 to n - 1 do
        b.(i) <- b.(i - 1) + a.(i)
    done;

    let count_guest happiness =
        let count i =
            let rec loop l r =
                if l = r then l - 1 else
                    let m = (l + r) / 2 in
                    if a.(m) + a.(i) < happiness then loop l m else loop (m + 1) r
            in
            loop 0 n
        in
        let rec loop i acc =
            if i = n then acc else
                let v = count i in
                if v < 0 then acc else
                    loop (i + 1) (acc + v + 1)
        in
        loop 0 0
    in

    let rec loop l r =
        if l = r then l else
            let mm = (l + r) / 2 in
            let count = count_guest mm in
            if count > m then loop (mm + 1) r else loop l mm
    in
    let target = loop 0 200000 in

    let calc_happiness target =
        let count lim i =
            let rec loop l r =
                if l = r then l - 1 else
                    let m = (l + r) / 2 in
                    if a.(m) + a.(i) < target then loop l m else loop (m + 1) r
            in
            loop 0 (min lim n)
        in
        let rec loop i rest acc =
            if i = n then rest * (target - 1) + acc else
                let v = count rest i in
                let h = if v < 0 then 0 else a.(i) * (v + 1) + b.(v) in
                    loop (i + 1) (rest - v - 1) (acc + h)
        in
        loop 0 m 0
    in
    calc_happiness target |> Printf.printf "%d\n"
)