Maximum Contiguous Subarray Sum

You are given two sequences of integers, (a) and (b), each of length (n), and an integer (k). Although (k) and the sequence (b) are provided as part of the input, they do not affect the outcome of this problem. Your task is to compute the maximum contiguous subarray sum of the sequence (a).

In other words, for the array (a = [a_1, a_2, \dots, a_n]), find

[ S = \max_{1 \le i \le j \le n} \left(\sum_{k=i}^{j} a_k\right). ]

This is a classic problem that can be solved efficiently using Kadane’s algorithm.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. Each test case consists of three lines:

1. The first line contains two integers (n) and (k) ((1 \le n \le 10^5), (0 \le k \le n)). Note that (k) is provided for distraction and will not affect the result.
2. The second line contains (n) space-separated integers representing the array (a).
3. The third line contains (n) space-separated integers representing the array (b) (this array is not used in computing the result).

It is guaranteed that the sum of (n) over all test cases does not exceed (10^6).

outputFormat

For each test case, output one line containing a single integer—the maximum contiguous subarray sum of the array (a). The answer for each test case should be printed on a new line to standard output (stdout).## sample

5
5 2
1 5 3 1 2
2 1 3 4 5
4 0
4 3 2 1
5 6 7 8
6 1
10 20 30 40 50 60
6 5 4 3 2 1

12
10
210