消毒柜里有 $n$ 种筷子，这 $n$ 种筷子被编号为 $1$ 到 $n$。第 $i$ 种筷子有 $a_i$ 支。两支不同的筷子可以组成一双，当且仅当它们属于同一种类。每支筷子最多只能属于一双筷子。请找出最少需要从消毒柜中取出多少支筷子，使得无论具体取出了哪些筷子，它们都至少能组成 $m$ 双筷子。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^6$) — 测试用例的数量。接下来是 $T$ 个测试用例的描述。

对于每个测试用例：

第一行包含两个整数 $n, m$ — 筷子的种类数和需要组成的筷子双数。保证 $1 \le n \le 10^6$，$1 \le m \le 10^{15}$，且 $\sum n \le 10^6$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示第 $i$ 种筷子的数量（$1 \le a_i \le 10^9$）。

输出格式

对于每个测试用例，输出一个整数，表示最少需要取出的筷子数量。如果不存在满足条件的最少数量，输出 -1。

样例

输入样例 1

3
3 4
6 2 3
3 114514
6 2 3
3 3
6 2 3

输出样例 1

10
-1
8

说明

设 $b_i$ 表示从消毒柜中取出的第 $i$ 种筷子的数量。

在第一个样例中，如果 $(b_1, b_2, b_3) = (5, 1, 3)$，那么取出的筷子总数是 9，但在这种情况下只能组成 3 双筷子。因此答案必须大于 9，可以证明答案是 10。