题目描述

一个长度为n数组A的最大连续和，是指所有满足1 ≤ L ≤ R ≤ n的 的最大值。

一次交换操作是指交换两个不同位置的元素A[i]、A[j]，也即执行如下步骤：

(1)选择两个下标i和j(i ≠j)

(2)进行赋值， ![]

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

输入格式

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

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

输出格式

输出答案

样例

样例​1​输入

10 2

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

样例​1​输出

32

样例​2​输入

5 10

-1 -1 -1 -1 -1

样例​1​输出

-1

数据范围

所有的数据满足,-10​^4<=A[i]<=10^4​。 本OJ测试时开启O2,可以认为1秒钟可以运算4亿次