Under construction

Still being built. Things may change

Assimilation

Time limit1sMemory limit512 MB

Summary
Given n planets with populations and k starting ships, an invasion needs ships >= population and a mobilization on a conquered planet yields ships equal to its population; find the minimum mobilizations to conquer all planets, or -1.
Level

Medium7 of 10

Topics
Greedy, Sorting, Math, Implementation
Solved
No attempts yet

Problem

An enlightened race of aliens plans to assimilate a star system, to help its inhabitants achieve perfection. They may resist, but as you are all well aware, resistance is futile.

There are n planets in the system, inhabited by a1, a2, . . . , an people, respectively. Aliens start with k assimilation ships and are allowed to make any of the following moves:

  • An invasion requires landing on a planet with some part of the fleet. The number of landing ships s must be greater or equal to the population m of the planet. After the invasion, these ships disappear, the planet is conquered and now has m + s inhabitants.
  • A mobilization creates, from a conquered planet, a number of new ships equal to the population of the planet. Every planet can be mobilized at most once.

For Aliens, invasions are easy and natural, but mobilizations turn out to be a bit tricky. Help them conquer all the planets in the system with minimal possible number of mobilizations.

Input

The first line of input contains the number of test cases z (1 ≤ z ≤ 30). The test cases follow, each one in the following format:

The first line of every test case contains two integers n and k (1 ≤ n ≤ 200 000; 1 ≤ k ≤ 109) – the number of planets, and the size of Aliens’ initial fleet. The second line contains n integers a1, . . . , an (1 ≤ ai ≤ 109) – the populations of the respective planets.

The sum of n values over all test cases does not exceed 500 000.

Output

For every test case, output a single integer: the minimal number of mobilizations required to conquer all the planets. If such conquest is impossible, output −1 instead.

Examples1

  1. Example 1

    Input
    4
3 15
6 5 26
3 15
6 5 27
2 1000000000
500123123 497000000
7 2
6 2 4 1 9 3 12
    Expected output
    2
-1
0
4