题目背景

Source: AMPPZ 2019.

题目描述

一群开化的外星种族计划同化一个恒星系统，以帮助其居民臻至完美。他们可能会抵抗，但——正如你们所深知的那样——抵抗是徒劳的。

该星系中有 $n$ 颗行星，其上分别居住着 $a_1, a_2, \ldots, a_n$ 个居民。外星人初始拥有 $k$ 艘同化飞船，并允许执行以下任意操作：

• 入侵 (invasion) 需要派遣部分舰队登陆行星。
  登陆飞船数量 $s$ 必须大于或等于该行星人口 $m$。
  入侵后，这些飞船消失，该行星被征服 (conquered) 且人口变为 $m + s$。

• 动员 (mobilization) 可从一颗被征服的行星上，创造等同于该行星人口数量的新飞船。
  每颗行星最多仅可被动员一次。

对外星人而言，入侵轻松而自然，但动员却略显棘手。请帮助他们以尽可能少的动员次数征服所有行星。

输入格式

本题单个测试点内有多组测试数据。

第一行一个整数，表示测试数据组数 $z$ $(1 \le z \le 30)$。

随后依次描述 $z$ 组测试数据，每组测试数据格式如下：

• 每组数据第一行包含两个整数 $n$ 和 $k$ $(1 \le n \le 200\,000; 1 \le k \le 10^9)$
  ——行星数量及外星人初始舰队规模。
• 第二行包含 $n$ 个整数 $a_1, \ldots, a_n$ $(1 \le a_i \le 10^9)$
  ——各行星的人口数量。

所有测试用例的 $n$ 值总和不超过 $500,000$。

输出格式

对每个测试用例，输出一个整数：征服所有行星所需的最小动员次数。

若无法完成征服，则输出 $\texttt{-1}$。

4
3 15
6 5 26
3 15
6 5 27
2 1000000000
500123123 497000000
7 2
6 2 4 1 9 3 12

2
-1
0
4