Description
Pocky is a sweet snack food, a biscuit stick that is very delicious!
As we are a CS students, our Pocky is described by 1D array with length N blocks. The pocky could be eaten from the most left or most right.
Also since 福昌 is a light eater, he won't eat all of the pocky, as he only can eat K blocks, however he want the maximum value from eating K blocks
For example given the Pocky array:
If the K = 3, The maximum value can be gathered from eating from the right block three times, as total value = 1 + 15 + 2 = 18
If the K = 5, The maximum value could be get by eating 2 block from the right side, and then 3 block from the left side, as total value = 1 + 15 + 1 + 7 + 8 = 32
Your task is to calculate the maximum value from given Pocky array and K.
There are 2 ways to solve this problem
1. Make 2 prefix sum from beginning of the array and end of the array, and compare each value related to K
2. Try to do this iteratively:
Calculate the sum of first K elements
Calculate the sum of first K-1 elements and one lastest element
Calculate the sum of first K-2 elements and 2 lastest elements
And so on ...
until you calculate sum of lastest K elements
Input
There are T testcases
Each testcase has
- N and K, separated by space in the first line
- ao, a1, a2, ..., aN-1 in the second line
1 <= T <= 50
1 <= K <= N <= 50000
1 <= ai <= 109
Output
print the maximum value followed by newline character for each testcase