核心思想

使用滑动窗口 + 前缀和，将窗口移动时的成本更新优化到O(1)。

关键观察

当窗口从[i, i+m-1]滑动到[i+1, i+m]时：

• 正序成本变化：移除权重为1的a[i]，所有其他元素权重减1，添加权重为m的a[i+m]
• 逆序成本关系：逆序成本 = (m+1) × 区间和 - 正序成本

题目内容

为了迎接即将到来的$2025$星穹铁道演唱会，米小游团队承担了舞台的布置工作。

舞台视为一个圆柱体，等分为 $n$ 块位置。每块位置建造台阶的成本为 $a_i$ 。

你需要在这些位置中选择连续的 $m$ 块进行建造(由于是圆形舞台，所以位置 $n$ 与位置 $1$ 也是相邻的)。记这连续的 $m$ 块成本组成数组 $b=${ $b_1,b_2,...,b_m$ }，你可以按正序或逆序的顺序建造。

若按正序建造，总成本为$\sum^m_{j=1}j×b_j$；若按逆序建造，总成本为 $\sum^m_{j=1}j×b_{m+1-j}$。

请计算并输出最小的建造成本。

输入描述

第一行输入两个整数 $n,m(1≦m≤n≦2×10^5)$ ，分别表示舞台等分块数和需要选择的块数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦ 10^5)$ 表示每块建造台阶的成本。

输出描述

输出一个整数，表示最小建造成本。

样例1

输入

5 3
1 4 3 1 2

输出

8

说明

在第一个样例中，选择位置 $4,5,1$ (对应成本 $b =${ $1,2,1$ })时，正序逆序建造的总成本一样小，等于 $1×1+2×2+3×1=8$ 。

样例2

输入

5 1
3 1 4 1 5

输出

1

说明

在第二个样例中，$m =1$ ，直接选择成本最小的块，得到最小成本 $1$ 。