
object Main extends App {

  val Array(n, k) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
  val v = scala.io.StdIn.readLine.split(" ").map(_.toInt)

  var memo: Map[(Array[Int], Int), Int] = Map()

  def dp(vv: Array[Int], k: Int): Int = {
    //println(v.deep, k, have)
    val have = v diff vv

    if (k <= 0) {
      memo = memo + ((vv, k) -> 0)
      return 0
    } else if (memo.isDefinedAt((vv, k))) {
      return memo((vv, k))
    } else {
      if (vv.length == 0) {
        if (have.forall(_ < 0)) {
          (0 to k).foreach { i =>
            memo = memo + ((vv, i) -> 0)
          }
          return 0
        }
        else {
          val tmp = List(
            -have.min + dp(Array(have.min), k - 1),
            0
          ).max
          (0 to k).foreach { i =>
            memo = memo + ((vv, i) -> tmp)
          }
        }
      }
      if (have.isEmpty) {
        val tmp = List(
          vv(0) + dp(vv.tail, k - 1),
          vv.last + dp(vv.init, k - 1),
          0
        ).max
        (0 to k).foreach { i =>
          memo = memo + ((vv, i) -> tmp)
        }

      } else {
        val tmp = List(
          vv(0) + dp(vv.tail, k - 1),
          vv.last + dp(vv.init, k - 1),
          -have.min + dp(vv :+ have.min, k - 1),
          -have.min + dp(have.min +: v, k - 1),
          0
        ).max
        (0 to k).foreach { i =>
          memo = memo + ((vv, i) -> tmp)
        }
      }
    }
    memo((vv, k))
  }


  println(dp(v, k))
}
