Maximize Score

You are given an array ‘arr’ of size ‘N’. Your task is to maximize your score by doing the following operation at most ‘K’ – times.

1. Choose an element from the start or end of the array and the value of the element to your score.
2. Remove the element from the array you have chosen in step – 1.

Note:

Initially, you have a score of zero.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’, denoting the length of the array and the maximum number of operations you can make respectively.
The second line of each test case contains ‘N’ space-separated integers denoting the values of array elements.

Output Format:

For each test case, print the maximum score you can make.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 5
1 <= N <= 5000
1 <= K <= N
1 <= arr[ i ]  <= 10^5

Where ‘T’ is the number of test cases, ‘N’  is the size of the array, ‘K’ is the maximum number of operations you can make, and ‘arr[ i ]’ is the value of the ith element of the array.

Time Limit: 1 sec

Note:

 You do not need to print anything, it has already been taken care of. Just implement the given function.