NKLEAVES - Leaves

One beautiful autumn day Radu and Mars noticed that the garden alley where they usually spend time is rather full of leaves. They decided to gather all the leaves in exactly K piles. The alley is a straight line and they established a coordinate system on the alley, with the origine at the beginning of the alley.

There are N leaves of various weights on the alley, all lined up, and the distance between each consecutive leaves is 1. More precisely the first leaf is at coordinate 1, the second at coordinate 2, ... , the N-th at coordinate N. Initially the two guys are at coordinate N.

The leaf gathering operation takes place as Radu and Mars leave the garden, so the leaves can only be moved to the left. The cost of moving a leaf is equal to its weight times the distance it is moved. Obviously one of the K piles will be at coordinate 1, but the rest can be anywhere.

Task

Find out the total minimum cost of gathering the N leaves in exactly K piles.

Input

The input contains on the first line two positive integers, N and K, separated by a space, having the significance given above. The following N lines contain N positive integers representing the weights of the leaves (line i+1 contains the weight of the leaf located at coordinate i).

Output

The output will contain a single line on which the minimum cost for gathering all the leaves in exactly K piles will be written.

Constraints

  • 0 < N < 100 001
  • 0 < K < 11, K < N
  • 0 < the weight of any leaf < 1 001

Example

Input
5 2
1
2
3
4
5

Output
13

It would be best to form the 2 piles in points 1 and 4. Leaves 1, 2 and 3 are taken to coordinate 1, and 4 and 5 are taken to coordinate 4. The total cost is:

1 * 0 + 2 * 1 + 3 * 2 + 4 * 0 + 5 * 1 = 13


Added by:Jimmy
Date:2007-12-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:Campion 2005

hide comments
2018-04-02 10:38:22
cant i use python?
2014-03-20 21:18:24 Ayush Awasthi
what does a green 0 in the result mean? please help i am new to this format of coding.
2011-04-08 01:17:11 Jagadish Rath
I am new to this place.... what does the number under RESULT column mean in submission status ?
2010-10-22 11:49:12 Erel Segal
I got better results with:
unsigned long long
in C++
2010-10-20 12:24:48 Erel Segal
Note that the cost may be larger than the maximum long integer value! I got best results with double.


Last edit: 2010-10-20 12:41:00
2010-10-19 21:16:25 H Shul
Sami - Acording to the problem description, leaves can only be taken toward position 1, i.e., it can not go to a 'higher' position and, therefore, position 1 must have a pile at the end
2010-08-22 19:20:52 InCore
i think it would be better if we put the first pile at pos 5 and the second at pos 3 so
5*0 + 4*1 + 3*0 + 2*1 + 1*2 =8<13
right???!!!!!!
2010-01-18 16:28:48 Siwakorn Srisakaokul


Last edit: 2010-01-20 03:19:14
2009-04-25 14:48:08 Srivatsan B
what is slope optimize?
2009-04-25 14:45:30 Srivatsan B
what is slope optimize...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.