#1587. 叶子合并leaves

内存限制:162 MiB 时间限制:5 Sec

题目描述

在一个美丽的秋天,丽丽每天都经过的花园小巷落满了树叶,她决定把树叶堆成K堆,小巷是笔直的 共有N片树叶(树叶排列也是笔直的),每片树叶都有一个重量值,并且每两片想邻的树叶之间的距离都是1 现把所有的树叶按从左到右的顺序进行编号,编号为1..N。丽丽移动每片树叶所消耗能量等于这片树叶的重量 乘以移动的距离,丽丽决定分K天完成,每天堆一堆,并且规定只能把树叶往左移动,因为丽丽每天都是从右往左 经过小巷的。求丽丽完成任务所消耗的最少能量。

输入格式

输入的第一行为两个用空格隔开的正整数N和K。后面有N行 每行一个正整数表示叶子的重量(第i+1行表示第i片树叶的重量)

输出格式

输出为一个整数,表示把树叶堆成K堆所消耗的最少体力。

样例

样例输入


			
5 2
1
2
3
4
5

样例输出


			
13

数据范围与提示



N在(0,1001)
K在(0,11)
每片树叶的重量(0,1001)