Hide

Problem E
Alice in the Digital World

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$.

Input

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}$.

Output

For each dataset, output the maximum weight.

Sample Input 1 Sample Output 1
1
6 2
1 3 2 6 2 4
12

Please log in to submit a solution to this problem

Log in