题目描述

喜欢吃麦当劳的光头强要在学校呆 $n$ 天，如果第 $i$ 天光头强吃到了麦当劳，他可以获得 $a_i$ 点快乐值。然而光头强不能吃太多麦当劳，在连续的 $m$ 天中，他最多只能有一半的天数吃麦当劳。请问光头强在这 $n$ 天中最多可以得到多少快乐值？

输入格式

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

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

一行一个整数表示答案。

Samples

4 3
1 2 3 4

5

数据范围

对于 $100\%$ 的数据，$2≤n≤100000,2≤m≤8,1≤a_i≤10000$。