let () = Scanf.scanf "%d %d\n" @@ fun n k ->
  let vs = Array.init n @@ fun _ -> Scanf.scanf "%d " @@ fun v -> v in
  Printf.printf "%d\n" @@
  Array.fold_left (Array.fold_left max) min_int @@
  Array.init (min n k + 1) @@ fun i ->
    Array.init (min n k + 1 - i) @@ fun j ->
      let a = Array.make (i + j) 0 in
      for k = 0 to i - 1 do
        a.(k) <- vs.(k)
      done;
      for k = 0 to j - 1 do
        a.(k + i) <- vs.(n - 1 - k)
      done;
      Array.sort (fun v v' -> compare v' v) a;
      Array.fold_left ( + ) 0 @@
      Array.sub a 0 @@ max 0 @@ 2 * i + 2 * j - k