Description

给你N个数字，将这些数字随机地摆成一圆，求必有的相邻M个数字之和的下限是多少（此下限不一定可以得到，只是求出下限即可）

Format

Input

第一行输入两个整数N，M。 第二行输入N个正整数

Output

输出和的最小值

Samples

10 3
1 2 3 4 5 6 7 8 9 10

17

Declare

原题目中，“必有的相邻M个数字之和的下限”指的是，对于任何一种随机的排列，必然存在至少一个相邻的M个数字的和，大于等于该下限，即：

$$\forall \pi \in Sym(A) \exist i \in \{ 0, 1, \dots, N-1 \} such\ that \sum_{k=0}^{M-1} \pi_{(i+k) \mod N} \geq X $$

其中，$A$表示给定的$N$个数字，$Sym(A)$表示$A$的所有排列的集合，$X$即为我们要求的下界。