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

hide comments
2020-04-23 09:40:50
testcase for debugging:
1
1 100000000
100000000

Output:
14999999950000000
2019-10-20 05:32:35
Had a hard time getting the green bar with Python here, but a couple of insights got me well out of TLE territory. Another great problem from cegprakash, I don't think I've ever passed one from this setter without learning something.
2017-09-23 17:43:15 Prabhakaran
GCC gave me ceil of sqrt(N) (where N is above 14*10^16)
x = sqrt(N); x*x > N

Usually we expect floor.

Very nice problem, Took a week to figure out this bug.
2016-12-18 14:50:14 Vipul Srivastava
Nice question..!!
2015-12-16 16:37:08 Prateek Agarwal
BEAUTIFUL RPOBLEM!! Thanks for sharing this with us @cegprakash!
2015-04-06 10:30:22 mehmetin
I was accepted with g++ 4.3.2, but getting WA with g++ 4.9.2. I think I am having precision errors when converting from double to long long. Is there some simple way to avoid these precision errors?
(edit) I found a way but it works slower.

Last edit: 2015-04-06 13:15:55
2015-02-09 12:41:06 (Tjandra Satria Gunawan)(曾毅昆)
using function pointer lead me to the slowest one :p
2015-02-07 01:38:37 cegprakash
No. Please generate a test file and compare your code's output with a brute force solution.
2015-02-04 16:25:07 Vamsi Krishna Avula
@cegprakash, can you please give me a test case where my solution fails?

Last edit: 2015-02-04 16:25:26
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.