Description
Stepmania is a widely played game among Otakus. Mr. SuBaRaSi has always wanted to become an Otaku.
So he wanted to be a maestro in Stepmania. However, it would take a lot of time to practice.
For each song, some parts are difficult while other parts are easy. For example, the chorus at the middle part of the song
might be hard that he need to practice 25 times in order to get familiar. On the other hand, the intro part might be easy that he
only need to practice 5 times.
He found it is NOT efficient to always practice from the start all the way to the end of the song. As in the previous example,
he can start at the chorus part till the end for 20 times, and from intro to the end 5 times, which might be more efficient.
However, since is not good for him to interrupt at too many different parts, he can ONLY start or stop at the breakpoints settled.
Given a song that contain n parts that numbered from 1 to n, and the difficulty of every part (number of times
needed to practice). Now he is limited to set at most k breakpoints between two adjacent parts of the song.
Then for each practice, he can start at the beginning or any of the breakpoints, and stop at the end
or any of the breakpoints. The time needed for each practice is exactly the number of parts practiced.
For example, if he started at part 3 and ended at part 7, then the time needed is (7-3+1) = 4.
You are to write a program that help SuBaRaSi to set up the breakpoints and arrange his practice so that
the total sum of his practice time is minimum. In this way, he will thank you because he can then achieve
his Otaku's dream more quickly.
Input
The input may contain many cases. In each case, the first line contain
two integers n, k (1<=n<=500, 1<=k<=123) representing the number of parts in the song
and the maximum number of breakpoints SuBaRaSi can set. In the following n lines, the i'th line
contain exactly one integer di (0<=di<=1000) denoting the difficulty of that part.
Output
For each case, print exactly one integer on a line representing the minimum time needed for SuBaRaSi to
become proficient in this song.