Description

A program a day keep girls away.

~by anonymous programmer

You are a programmer, you need to write code day and night.

In order to keep you in a sharp mind, you drink a lot of coffee.

Given n cups of coffee, the ith cup of coffee has the effect that make

you write ai lines of code and ai will be decreasing order.

Each cup of coffee can only be drunk for once.

You can drink coffee in arbitary order!!!!

You need to write m lines of code.

In a day when you drink a cup of coffee,

the second cup of coffee will loss it's effect by 1

and the third cup of coffee will loss it's effect by 2

..... and so on

You need to find out what's the minimum number of days

that you can finish m lines of code.

 

Example:

Given n = 5 cups of coffee, you need to finish m=16 lines of code.

The effect of coffee = a1 = 5, a2 = 5, a3 = 5, a4 = 5, a5 = 5

If you drink a1~a4 at the first day, you finish 5 + (5-1) + (5-2) + (5-3) = 14 lines of code.

If you drink a5 at the second day, you finish 5 lines of code.

14+5 >= 16 therefore you can finish your code by 2 days,

and it's the minimum number of days that you can achieve.

Input

First line contains one integer t(1 <= t <= 10) which means the number of testcases.

Each testcases contains two lines.

First line contains two integer n(1 <= n <= 2*10^5), m(1 <= m <= 10^9)

Second line contains n numbers ai(1 <= ai <= 10^9)

Output

For each testcase print only one number which means the minimum number of days

that you can finish m lines of code.

If you can't finish your code in any way, print -1.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss