插入排序和希爾(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