동화

계몽된 외계 종족이 한 성계를 동화하여 주민들이 완벽에 도달하도록 돕고자 한다. 주민들이 저항할 수도 있지만, 여러분도 잘 알다시피 저항은 무의미하다.

성계에는 n개의 행성이 있고, 각 행성의 인구는 a1, a2, . . . , an이다. 외계인은 k척의 동화 함선으로 시작하며 다음 행동 중 아무거나 할 수 있다.

• 침공은 함대의 일부를 행성에 착륙시켜야 한다. 착륙하는 함선의 수 s는 행성의 인구 m보다 크거나 같아야 한다. 침공 후 이 함선들은 사라지고, 행성은 정복되어 인구가 m + s가 된다.
• 동원은 정복한 행성에서 행성 인구만큼의 새 함선을 만든다. 각 행성은 최대 한 번만 동원할 수 있다.

외계인에게 침공은 쉽고 자연스러운 일이지만, 동원은 다소 까다롭다. 이들이 최소한의 동원 횟수로 성계의 모든 행성을 정복하도록 도와라.

첫 줄에는 테스트 케이스의 수 z가 주어진다 (1 ≤ z ≤ 30). 테스트 케이스가 이어지며, 각 테스트 케이스의 형식은 다음과 같다.

각 테스트 케이스의 첫 줄에는 두 정수 n과 k가 주어진다 (1 ≤ n ≤ 200 000; 1 ≤ k ≤ 109). 각각 행성의 수와 외계인의 초기 함대 규모이다. 둘째 줄에는 n개의 정수 a1, . . . , an이 주어진다 (1 ≤ ai ≤ 109). 각 행성의 인구이다.

모든 테스트 케이스의 n 값의 합은 500 000을 넘지 않는다.

각 테스트 케이스마다 정복에 필요한 최소 동원 횟수를 한 정수로 출력한다. 정복이 불가능하면 −1을 출력한다.