Go Back
Don't You Worry Child (Surprise Problem) (100)
Description

Problem Author: Omkar Prabhu
When we thought of this contest at first, we all were like, “wow, we would tell our college stories!" and soon we all realised that time really flied in these 4 years...

What did we care about the most in these 4 years? Marks? Attendance? Assignments? Huh, NO!
We made sure we are learning in all aspects and get inspired every single day to come up with new ideas and new projects or something new to keep us happy.

Want to feel that vibe to come to college for your remaining years? Find that "one thing" which you feel interesting. No matter what it is, it can be music, academics, tech, drama, dance, logistics, marketing, just get into that damn thing and explore!

But, we all experienced one common thing, "ye semester chod, agle semester pakka 7+ or 8+ or 9+ launga!". So here you are.
You will be given marks of N subjects and you are given S semesters. Let's define an array A with size N x S as the array that's formed by concatenating S copies of N.

For example, if N = {6, 9} and S = 3, then A = {6, 9, 6, 9, 6, 9}.

You have to find the maximum subarray sum of the new array. Fomally, you should compute the maximum value of Ai + Ai+1 + Ai+2 + ... + Aj, where 0 ≤ i ≤ j ≤ (N x S).

Input

The first line of the input contains a single integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and S.
The second line contains N space-separated integers.

Output

For each test case, print a single line containing the maximum subarray sum of the new array A.

Constraints

1 ≤ T ≤ 25
1 ≤ N, S ≤ 104
-102 ≤ Ni ≤ 102

Example
Copy Input

Input:
2
2 3
1 2
3 2
1 -2 1

Output:
9
2

Explanation

Case 1: A = {1, 2, 1, 2, 1, 2} and the subarray with maximum sum is the whole {1, 2, 1, 2, 1, 2}. So the answer is 9.
Case 2: A = {1, -2, 1, 1, -2, 1} and the subarray with maximum sum is {1, 1}. So the answer is 2.

Good Bye Batch 15-19
#OneLastTime Contest from Batch of 2015-19 of SIES GST



Announcement
Surprise Problem Added!
Contest is extended by 24 hours!

Problem Tags
math, dp

Supported by our Coding Partner