题目描述

有n个宽度为1、并排的山洞，每个山洞里都藏着金币。

山洞前有一扇宽度为k的石门，被石门挡住的山洞不能进入。你有一次施展魔法的机会，可以让石门平移到任意连续的k个山洞前。从此石门位置被锁定。

你必须在石门锁定后才能走进山洞，不能先拿金币再移动石门。

已知每个洞里藏着的金币数量，问你最多能拿到多少个金币。

输入格式

第一行一个正整数，为山洞数量n(10≤n≤100)；

第二行一个正整数，为石门宽度k(1≤k≤n)；

第三行输入n个正整数（大小在1~20范围内），相邻两个正整数用一个空格分隔。按从左到右的顺序，每个正整数表示一个山洞里藏着的金币数量。

输出格式

一个整数，为你最多能拿到金币的数量。

输入/输出样例

5 3
7 2 12 5 3

10

7 3
4 18 2 10 7 16 1

39

样例1解释

有5个山洞，石门宽度为3，每个山洞的金币数量是7，2，12，5，3。

你有3种拿金币的方法：

1.让石门移动到最左边，拿右边两个山洞的金币，共8个；

2.让石门移动到正中间，拿两头山洞的金币，共10个；

3.让石门移动到最右边，拿左边两个山洞的金币，共9个；

你最多能拿到10个金币，第3个山洞无论如何都进不去。

说明/提示

时间1000ms，内存256MiB