像往常一样,Sereja 有数组 a,其元素是整数:a[1]、a[2]、...、a[n]。我们来介绍一下符号:
$$f(a,l,r) = \sum_{i=l}^{r} a[i]; \quad m(a) = \max_{1 \leq l \leq r \leq n} f(a,l,r).$$
交换操作是以下操作序列:
- 选择两个索引 i, j (i ≠ j);
- 执行赋值 tmp = a[i], a[i] = a[j], a[j] = tmp。
如果允许 Sereja 执行最多 k 次交换操作,他可以得到函数 m(a) 的最大值是多少?
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 200; 1 ≤ k ≤ 10)。下一行包含 n 个整数 a[1], a[2], ..., a[n] ( - 1000 ≤ a[i] ≤ 1000)。
输出
在单行中打印 Sereja 在允许执行最多 k 次交换操作的情况下可以获得的 m(a) 最大值。
示例
输入 #1
10 2 10 -1 2 2 2 2 2 2 -1 10
输出 #1
32
输入 #2
5 10 -1 -1 -1 -1 -1
输出 #2
-1