最小子序列和

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给你一个长为n(10<=n<=10000)的数组,数组中的每一个数大于等于1小于等于1000000。请你找出一个长为k(100<=k<=1000)的子序列。找序列时,假如第一个数找的是数组中的第i个位置的数,那么找第二个数时只能找数组中第i个位置后的数,依次找出k个数。使得第一个数*1+第二个数*2+...+第k个数*k的值最小。 

Input

 有多组(小于11组)测试数据,每组第一行输入nk(用空格隔开),第二行输入n个数(数之间用空格隔开)。

Output

 请输出最小的和。

Sample Input

15 5
5 4 3 2 1 1 2 3 4 5 5 4 3 2 1

Sample Output

19

Hint

 

Source