采矿2

题面描述

现在有 $N$ 个矿场，他们各自矿物的质量依次为 $A_1$ $A_2$ $\dots$ $A_N$ 。John 要开始采矿。具体地，他可以选择从一个矿场出发，然后采掘这个矿场之后的任意 $M$ 个矿场（起始矿场可选）。例如，若他从 $2$ 号矿场出发且 $M=3$，他一定采掘的矿场是 $A_2$，可能采掘的矿场是 $A_7$ $A_{11}$ 或 $A_6$ $A_8$ 等等。

采矿也不断升级了 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

29

样例 #2

样例输入 #2

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

样例输出 #2

76

提示

数据范围与约定

• 对于 $10\%$ 的数据，满足 $N\leq 10$。

  对于 $50\%$ 的数据，满足 $N\leq 200$。

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