题目描述Description

最近，小明经常网上冲浪，但是在冲浪之余，他总会感觉有一些失落感。他不明白他为什么会失落。明明已经想好要摆烂了。为什么还是会这么痛苦，而且他发现。不光是他，他周围的大部分人，往往都是嘴上说着摆烂。但是背地里却在努力偷偷卷。小明很失落。他意识到了能够接受自己的软弱。开心的摆烂也是一件很难的事。但是如果不摆烂。他的精神状态会很差。并且会错过很多互联网上有趣的事。现在新的学期开始了。这个学期一共有n天。如果他在第i天摆烂，他能获得ai点的快乐值。但是他不能接受自己一直摆烂。所以他给自己定了一个规矩。在连续的m天中。他最多只能有一半的天数选择摆烂。问小明在这n天中最多可以得到多少快乐值。

输入格式Input

第一行包含两个整数n,m。(2\leq n\leq 100000,2\leq m\leq 8)

第二行包含n个整数，第i个整数表示a_i。（1\leq a_i\leq 10000)

输出格式Output

一行一个整数表示小明在n天中最多可以获得多少快乐值。

样例Sample

提示Hint

由于3天内摆烂次数不能超过一半。所以最优方案是第一天摆烂，第四天也摆烂，最后收获5点快乐

出题Author

徒手拆机甲

来源Source