插入排序和希尔(Shell)排序

部队中共有n个士兵，每个士兵有各自的能力指数xi，在一次演练中，指挥部确定了m个需要防守的地点，按重要程度从低到高排序，依次以数字1到m标注每个地点的重要程度，指挥部将选择m个士兵依次进入指定地点进行防守任务，能力指数为x的士兵防守重要程度为y的地点将得到x*y的参考指数。现在士兵们排成一排，请你选择出连续的m个士兵依次参加防守,使得总的参考指数值最大。

输入包含多组数据。

输入第一行有两个整数n,m(1<=n<=1000000，1<=m<=1000),第二行n个整数表示每个士兵对应的能力指数xi（1<=xi<=1000）。

对于30%的数据1<=m<=n<=1000。

输出一个整数，为最大的参考指数总和。

5 32 1 3 1 4

17