DIY: Divide Chocolate

Problem statement

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness. You have K friends that you want to share the chocolate with. You cut the chocolate using K cuts and get K + 1 pieces, where each piece consists of consecutive chunks. Since you are the host, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

Input

The input will be an array of integers representing the sweetness of chocolate pieces and an integer value of K. The following is an example input:

sweetness = {1, 2, 3, 4, 5}
K = 3

Output

The output will be an integer value representing the maximum sweetness we can get from the array. The following is an example output for the above input:

3

The chocolate can be divided into {1,2}, {3}, {4}, and {5}. We can either get the part {1,2} or {3}.

Coding exercise

Implement the maximizeSweetness(chocolate, K) function, where sweetness is the array of integers and K is the integer number that will divide the chocolate. The function will return a single integer value representing the amount of sweetness the host would get.