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 A_{i} + A_{i+1} + A_{i+2} + ... + A_{j}, 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 ≤ 10^{4}

-10^{2} ≤ N_{i} ≤ 10^{2}

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.