using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5 4");
WillReturn.Add("1 3 2 4 3");
//8
}
else if (InputPattern == "Input2") {
WillReturn.Add("6 3");
WillReturn.Add("3 7 1 5 6 4");
//21
}
else if (InputPattern == "Input3") {
WillReturn.Add("5 2");
WillReturn.Add("3 3 2 2 1");
//11
}
else if (InputPattern == "Input4") {
WillReturn.Add("12 5");
WillReturn.Add("864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728");
//4427122428
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long K = wkArr[1];
long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long Result = Solve(K, AArr.ToArray());
Console.WriteLine(Result);
}
static long Solve(long pK, long[] pAArr)
{
long Answer = 0;
long UB = pAArr.GetUpperBound(0);
// 最大スコア[1つ前の飴 , 2つ前の飴]
long[,] ScoreArr = new long[UB + 1, UB + 1];
// 飴を2個取る組み合わせを全列挙
for (long I = 0; I <= UB; I++) {
for (long J = 0; J <= I - 1; J++) {
long SumVal = pAArr[I] + pAArr[J];
ScoreArr[I, J] = SumVal;
Answer = Math.Max(Answer, SumVal);
}
}
// 最大値情報[1つ前の飴]
var SegTreeMaxInfoDict = new Dictionary<long, MaxInfoDef>();
for (long I = 0; I <= UB; I++) {
SegTreeMaxInfoDict[I] = new MaxInfoDef();
SegTreeMaxInfoDict[I].CurrInd = 0;
SegTreeMaxInfoDict[I].RunMax = 0;
}
// 3個目以降の飴を取る場合を全探索
for (long I = pK; I <= UB; I++) {
for (long J = I - 1; 1 <= J; J--) {
long RangeSta = 0;
long RangeEnd = Math.Min(J - 1, I - pK);
// 1点更新区間最大値のセグ木の更新
if (RangeSta <= RangeEnd) {
while (true) {
long CurrInd = SegTreeMaxInfoDict[J].CurrInd;
long RunMax = SegTreeMaxInfoDict[J].RunMax;
RunMax = Math.Max(RunMax, ScoreArr[J, CurrInd]);
SegTreeMaxInfoDict[J].RunMax = RunMax;
if (CurrInd < RangeEnd) {
CurrInd++;
SegTreeMaxInfoDict[J].CurrInd = CurrInd;
}
else {
break;
}
}
long GainVal = SegTreeMaxInfoDict[J].RunMax;
GainVal = Math.Max(GainVal, ScoreArr[J, RangeEnd]);
long NewVal = GainVal + pAArr[I];
ScoreArr[I, J] = Math.Max(ScoreArr[I, J], NewVal);
Answer = Math.Max(Answer, NewVal);
}
}
}
return Answer;
}
// 1点更新区間最大値のセグ木の更新待ちキューの構造体
class MaxInfoDef
{
internal long CurrInd;
internal long RunMax;
}
}