You are given an array A consisting of N integers and a special number K. You have to divide the array into K non-empty subarrays. The sum of elements of the 1^st, 3^rd, 5^th, 7^th...(odd) subarrays is the price at which you buy the stocks and the sum of elements of the 2^nd, 4^th, 6^th, 8^th....(even) subarrays is the price at which you sell the stocks. The profit of this transaction would be equal to = selling price - buying price, where the selling price is the sum of elements of the even indexed subarrays and the buying price is the sum of elements of the odd indexed subarrays.

Task

Determine the maximum profit you can make by buying and selling the stocks in an optimal manner.

Example

Assumptions

• N = 5
• A = [7, 7, 8, 2, 2]
• K = 2

Approach

• Check all the possible partitions of the array and take the one which gives the maximum profit
• Possible partitions are as follows [- (7) + (7 + 8 + 2 + 2), - (7 + 7) + (8 + 2 + 2), - (7 + 7 + 8) + (2 + 2), - (7 + 7 + 8 + 2) + (2)]
• The profits of these possible partitions are as follows [19 - 7, 12 - 14, 4 - 22, 2 - 24] = [12, -2, -18, -22] hence the answer is 12.

Function description

Complete the function solve provided in the editor. This function takes the following 3 parameters and returns the required answer:

• N: Represents the size of array A
• A: Represents the elements of array A
• K: Represents the special number

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button)

• The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • The first line contains a single integer N denoting the size of the array A.
  • The second line contains N space-separated integers denoting the elements of the array A.
  • The third line contains the special number K.

Output format

For each test case in a new line, print a single integer representing the maximum profit.

Constraints

\(1\leq T \leq 10\)

\(1\leq N \leq 10^4\)

\(-10^9\leq A_i \leq 10^9\)

\(1\leq K \leq min(N,10^2)\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.