采矿1

题面描述

现在有 $N$ 个矿场，他们各自矿物的质量依次为 $A_1$ $A_2$ $\dots$ $A_N$ 。 John 要开始采矿。具体地，他可以选择从一个矿场出发，然后采掘从这个矿场往后（包括起始矿场）的 $M$ 个矿场。例如，若他从 $2$ 号矿场出发且 $M=3$，他将会采掘的矿场一定是 $A_2$ $A_3$ $A_4$。

采矿也不断升级了 John 的采矿装备。采集他所选的第 $1$ 座矿时，John 采矿数量的倍率是 $100\%$，每采完一座矿，采矿收益就会使得 John 的采矿倍率提高 $100\%$。例如，John 采集他所选的第 $7$ 个矿场的采矿倍率为 $700\%$。

现在定义在每座矿场采矿的收益为 $采矿倍率\times矿物质量$，再定义 John 此轮采矿作业的收益为在每一座矿场采矿的收益之和，他想让你求出他能获得的最大总收益。

输入格式

输入共两行，第一行两个整数 $N,M$ 含义见题面，第二行 $N$ 个数，为 $A_1$ $A_2$ $\dots$ $A_N$。

输出格式

输出一个整数，代表 John 可能获得的最大总收益。

样例 #1

样例输入 #1

10 4
-5 0 2 -2 -1 7 -5 -1 -9 -1

样例输出 #1

23

样例 #2

样例输入 #2

10 4
1 7 3 5 0 -6 9 -1 8 3

样例输出 #2

44

提示

数据范围与约定

对于 $40\%$ 的数据，满足 $N\leq 2\times 10^3$。

对于 $70\%$ 的数据，满足 $N\leq 2\times10^5$。

对于 $100\%$ 的数据，满足 $1\ \le\ M\ \le\ N\ \le\ 1\ \times\ 10^7$，$ -\ 2\ \times\ 10^5\ \le\ A_i\ \le\ 2\ \times\ 10^5 $。

题目保证答案不超过 $10^{18}$，输入量较大，请注意 IO 读写速度对程序的效率影响。