Orange的管道

题目描述

Orange有一根长长的管道，里面存有 $n$ 个质量为 $a_i$ 的小球，Orange每次可以从管道的最左端或者最右端拿走一个小球，同时Orange最多只能拿走 $k$ 个球。

现在Orange想要将这根管子移动到另外一个地方，为了偷懒，他想要管道中小球的质量之和最小，你能告诉Orange他最小需要搬动多重的管道吗？（管道自身质量可以忽略不计）

输入格式

输入共2行，第一行包含2个整数 $n(n \leq 10^5)$ 和 $k (k < n)$，表示管道中球的数量，第二行 $n$ 个整数 $a_i(a_i \leq 10^9)$，表示第 $i$ 个球的质量。

输出格式

输出共一行，表示Orange需要搬动的管道的最小质量。

样例 #1

样例输入 #1

6 4
1 9 8 5 5 4

样例输出 #1

9

提示

显然，我们可以拿走管道的左边4个小球，最后剩下右边两个小球，质量之和为$5 + 4 = 9$，可以证明这是最优的。