The Robot Chef's Kitchen

Chef-Bot picks exactly ~K~ ingredients from either end of a row of ingredients.i.e. you robot can take an ingredient either from the left end or from the right end as needed. However any such split should total to exactly ~K~.

Each ingredient has a tastiness score which can vary between ingredients and can also be negative. Your goal is to write an algorithm to maximize the tastiness score so that robot can work independently.

The Task

Given ~N~ ingredients and integer ~K~, find the maximum total tastiness by taking some from the left end and the rest from the right end (total = ~K~).

Input Specification

The first line contains ~T~ — the number of dishes. Each dish is defined by two lines: Line 1: two integers ~N~ and ~K~ Line 2: ~N~ space-separated integers (tastiness scores for the ingredients)

Output Specification

• For each dish print one line of outpu: the maximum total tastiness score
• There would be ~T~ lines of output

Sample Input

2
6 4
1 12 -5 -6 50 3
5 3
10 2 3 1 8

Sample Output

66
20

Constraints

~1 \le T \le 100,000~
~1 \le K \le N \le 100000~
~-10000 \le tastiness \le 10000~

Test cases available here!