← 返回题目列表

Codeforces · 425/A

A. Sereja 和掉期

中文机器翻译题面 查看原题

像往常一样,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