题目描述

一个长度为 $n$ 的数组 $A$ 的最大连续子数组和，是指所有满足 $1\le L\le R\le n$ 的 $\sum_{i=L}^R A[i]$ 的最大值。

一次交换操作是指：

1. 选择两个下标 $i$ 和 $j$（$i\not=j$）；
2. 进行赋值：$tmp=A[i],A[i]=A[j],A[j]=tmp$。

给定一个长度为 $n$ 的数组，最多进行 $m$ 次交换操作后，求该数组的最大连续子数组和。

输入格式

第一行两个整数 $n$ 和 $m$。

第二行 $n$ 个整数，表示数组中的元素。

输出格式

输出答案。

输入输出样例 #1

输入 #1

10 2
10 -1 2 2 2 2 2 2 -1 10

输出 #1

32

输入输出样例 #2

输入 #2

5 10
-1 -1 -1 -1 -1

输出 #2

-1

说明/提示

数据范围

所有数据满足 $-10^4\le A[i]\le10^4$。