Merge Ropes :
Difficulty Level : Hard
Submissions : 227
Asked In :
Marks :10
: 8 | : 0
There are $$$n$$$ piles of ropes arranged in a row. The $$$i^{th}$$$ pile has $$$rope[i]$$$ ropes.
A move consists of merging exactly $$$k$$$ consecutive piles into one pile, and the cost of this move is equal to the total number of ropes in these $$$k$$$ piles.
Return the minimum cost to merge all piles of ropes into one pile. If it is impossible, return $$$-1.$$$
Input
The first line contains two integers, N $$$(1 \le N \le 30)$$$ and K $$$(2 \le K \le 30)$$$.
The second line contains an array of $$$N$$$ piles, $$$A_1,A_2...A_N$$$ $$$(1 \le A_i \le 100000)$$$
Output
Return the minimum cost to merge all piles of stones into one pile.
Examples
Input
4 2 3 2 4 1
Output
20
Input
4 2 6 4 4 6
Output
40
