#### K-Concatenation

You are given an array **A** with size **N** (indexed from 0) and an integer **K**. Let’s define another array **B** with size **N** · **K** as the array that’s formed by concatenating **K** copies of array **A**.

For example, if **A** = {1, 2} and **K** = 3, then **B** = {1, 2, 1, 2, 1, 2}.

You have to find the maximum subarray sum of the array **B**. Fomally, you should compute the maximum value of **B _{i} + B_{i+1} + B_{i+2} + … + B_{j}**, where 0 ≤

**i**≤

**j**<

**N**·

**K**.

### Input

- The first line of the input contains a single integer
**T**denoting the number of test cases. The description of**T**test cases follows. - The first line of each test case contains two space-separated integers
**N**and**K**. - The second line contains
**N**space-separated integers**A**._{0}, A_{1}, …, A_{N-1}

### Output

For each test case, print a single line containing the maximum subarray sum of **B**.

### Constraints

- 1 ≤
**T**≤ 10 - 1 ≤
**N**≤ 10^{5} - 1 ≤
**K**≤ 10^{5} - -10
^{6}≤**A**≤ 10_{i}^{6}for each valid**i**

### Subtasks

**Subtask #1 (18 points):** **N** · **K** ≤ 10^{5}

**Subtask #2 (82 points):** original constraints

### Example

Input:2 2 3 1 2 3 2 1 -2 1Output:9 2

### Explanation

**Example case 1:** **B** = {1, 2, 1, 2, 1, 2} and the subarray with maximum sum is the whole {1, 2, 1, 2, 1, 2}. Hence, the answer is 9.

**Example case 2:** **B** = {1, -2, 1, 1, -2, 1} and the subarray with maximum sum is {1, 1}. Hence, the answer is 2.

### Solution

Working on the solution.