CHICKEGG - Chicks

There are n hens in a farm. The egg laying ability of all the hens decreases by 1 day after each time they lay an egg. (i.e. every hen will lay the next egg 1 day slower than the time it took to lay the previous egg)

Let the initial egg laying ability of Hen[i] be D[i].

  • Hen[i] lays its first egg on D[i]th day.
  • Hen[i] lays its second egg on 2*D[i]+1 th day.
  • Hen[i] lays its third egg on 3*D[i]+3rd day.
  • Hen[i] lays its fourth egg on 4*D[i]+6th day.
  • Hen[i] lays its fifth egg on 5*D[i]+10th day.

and so on.

Given n - the number of hens and the array D - the initial egg laying ability of the hens, find the minimum number of days required to produce at least K eggs. You can safely assume that eggs neither gets damaged nor converted into hens.

Input

The first line consists of integers t, the number of test cases. For each test case, the first line consists two integers n and K. The next line consists of n integers representing the initial egg-laying ability of the hens.

Output

For each test case, find the minimum number of days required to produce at least K eggs.

Constraints

1 <= t <= 10^2
1 <= n <= 10^3
1 <= K <= 10^8
1 <= D[i] <= 10^8

Example

Sample Input:
3
1 4
1
2 5
2 5
5 1000000
1 2 3 4 5

Sample Output:
10
11
20000500003

Explanation of Test case #2

There are 2 hens and we need to produce 5 eggs

At time 2, Hen 0 lays an egg.

At time 5, Hen 0 and Hen 1 lay an egg each.

At time 9, Hen 0 lays an egg

At time 11, Hen 1 lays an egg.


Added by:cegprakash
Date:2015-01-06
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU SCM qobi

hide comments
2015-02-01 05:00:28 cegprakash
Let 'a' be the initial egg hatching ability of a hen.
First egg will be laid on ath day, Second egg on a + (a+1)th day, third egg on a+(a+1)+(a+1+1)th day and so on..

Last edit: 2015-02-01 05:43:58
2015-02-01 04:51:18 mala da.... annamala
how does the hen 0 lay the second egg at 5th day? after it lays its egg at d[0]=2, d[0] becomes 3. So it should lay its second egg on 2*d[0]+1 = 2*3+1=7th day right?

Last edit: 2015-02-01 04:55:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.