Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4075
Set

Time Limit: 2 Seconds      Memory Limit: 131072 KB

Chiaki is going to create $n$ sets $S_0,S_1,\dots,S_{n-1}$ under the following restrictions:

  • $|S_i| = m$.
  • $|S_i \setminus S_{(i-1+n) \bmod n}| \ge l_i$.
  • $|S_0 \cup S_1 \cup \cdots \cup S_{n-1}|$ should be minimized.

Note that $|S|$ means the size of set $S$ and $A \setminus B$ means set difference which is defined as $\{x:x \text{ in } A\text{ and }x\text{ not in }B\}$.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^6$, $0 \le m \le 10^{18}$) -- the number of sets and the size of each set.

The second line contains $n$ integers $l_0,l_1,\dots,l_{n-1}$ ($0 \le l_i \le 10^{18}$).

It's guaranteed that the sum of n in all test cases will not exceed $10^6$.

Output

For each test case, output an integer denoting the minimum value of $|S_0 \cup S_1 \cup \cdots \cup S_{n-1}|$. Or $-1$ if the restrictions cannot be satisfied.

Sample Input

2
3 1
1 1 1
3 2
1 1 1

Sample Output

3
3

Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status