Chiaki 打算创建 $n$ 个集合 $S_0, S_1, \dots, S_{n-1}$，并满足以下限制：

• $|S_i| = m$。
• $|S_i \setminus S_{(i-1+n) \pmod n}| \ge l_i$。
• $|S_0 \cup S_1 \cup \dots \cup S_{n-1}| = v$ 应当最小化。

注意 $|S|$ 表示集合 $S$ 的大小，$A \setminus B$ 是集合差，定义为 $\{x : x \in A \text{ 且 } x \notin B\}$。

给定数字 $n, m$ 和 $l_i$，求 $v$ 的最小值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^6, 0 \le m \le 10^{18}$)，表示集合的数量和每个集合的大小。 第二行包含 $n$ 个整数 $l_0, l_1, \dots, l_{n-1}$ ($0 \le l_i \le 10^{18}$)。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 $v = |S_0 \cup S_1 \cup \dots \cup S_{n-1}|$ 的最小值。如果无法满足限制，则输出 $-1$。

样例

样例输入 1

2
3 1
1 1 1
3 2
1 1 1

样例输出 1

3
3