Maximum Lantern Value

You are given a lantern with a base value \(B\) and a sequence of \(N\) attachments. Each attachment has an integer value. Your task is to choose a contiguous subarray of these attachments such that the sum of its elements is maximized, then add this maximum subarray sum to the base value \(B\). Formally, given an array \(a_1, a_2, \ldots, a_N\), you need to compute:

[ \text{Result} = B + \max_{1 \leq i \leq j \leq N} \left( \sum_{k=i}^{j} a_k \right) ]

If all attachment values are negative, the answer will be \(B\) added to the largest (least negative) attachment value.

inputFormat

The input begins with an integer (T) denoting the number of test cases. For each test case, the first line contains two integers (B) and (N) representing the base value and the number of attachments, respectively. The second line contains (N) space-separated integers which represent the values of the attachments.

outputFormat

For each test case, output a single line containing the maximum possible total lantern value.## sample

2
5 4
1 2 3 4
-5 3
-1 -2 3

15
-2