After returning from Wonderland, Alice needs to improve her scientific skills in the current digital world. Alice decides to participate the ACM - ICPC Asia Nha Trang Regional Contest 2016 to evaluate her actual performance. Her favorite problem in the contest is described below.
Given an array of positive integers $A = {a}_{1}, {a}_{2},\ldots , {a}_{n}$, a subarray ${A}_{i}^{j}$ of $A$ is a sequence of continuous elements in $A$, i.e., ${A}_{i}^{j} = {a}_{i}, {a}_{i+1},\ldots , {a}_{j}$ (where $1 \leq i \leq j \leq $ n). The weight of ${A}_{i}^{j}$ is the sum of all its elements, i.e., $\sum _{k=i}^{j} {a}_{k}$.
Given an integer $m$, your task is to find the maximum weight subarray of $A$ that contains only one $m$ as the minimum element. You can assume that $A$ always contains at least one element with value $m$.
The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $20$. The following lines describe the datasets.
Each dataset is described by the following lines:
The first line contains two positive integers $n$ and $m$ where $n \leq {10}^{5}$ and $m \leq {2}^{6}$;
The second line contains $n$ positive integers, each with value at most ${2}^{6}$.
For each dataset, output the maximum weight.
Sample Input 1 | Sample Output 1 |
---|---|
1 6 2 1 3 2 6 2 4 |
12 |