You are given an array of integers A of size N which represents the size of items laid on a row. You have to transfer all of the items to another place. In order for you to do so you have to pick a bag with a size S then start at the first item, place it into the bag and transfer it and move to the next item.

It is given that you can only pick the item at index i when A[i] <= S. Additionally, whenever you pick an item you add to a parameter called the wasted space parameter.

You are allowed to change the size of the bag at most K times while transferring the items.

Your task is to find the minimum value of the wasted space parameter to transfer all of the items using no more than K bag size changes.

Constraints

• 1<= N <= 400
• 1<= K <= 400
• 1<= arr[i] <= 10^3

Input Format For Custom Testing
The first line contains an integer, N, denoting the number of elements in arr.
The next line contains an integer,K, denoting the maximum number of bag size changes allowed.
Each line i of the N subsequent lines (where 0<= i <= N) contains an integer describing arr i.

Example 1 :

Input
2
1
1
2

Output
0

Explanation
You can start with a bag of size 1 and pick the first item then change to 2 and pick the second,this will result in a 0 wasted space.

Example 2 :

Input
3
1
1
1
1

Output
0

Explanation
You can start with a bag of size 1 and keep the same bag for all the items.

Example 3 :

Input
6
2
7
9
8
2
3
2

Output
3

Explanation
You can start with a bag of size 7, pick the first then change the bag size to 9 and pick the second and third items. Then change the size of the bag to 3 and pick the rest of the items.
The wasted space parameter will be calculated as follows: (7-7)+(9-9)+(9-8)+(3-2)+(3-3)+(3-2)=3.

----

If you got any intution or explanation or code or anything please tell in the comments it will be helpful. Thank you.