CODFURY - Megatron and his rage

Infuriated by the Decepticons' defeat after a long epic battle with the Autobots, Megatron, in his rage, has decided to destroy all the planets on his way back to Cybertron from Earth. There are multiple planets between Earth and Cybertron, and each planet has some number of Autobots to guard it from him. Since Megatron is low on ammo, he wants to fight as few Autobots as possible on his way back. He can defeat no more than "M" Autobots in total.

You need to find the maximum number of planets he can possibly destroy in his journey.

NOTE: Megatron can start his "destruction spree" from any planet, and can only move to the next planet from the planet he's currently on.

Input

You will receive one integer "T" denoting the number of test cases. (T <= 20)

Then, the next line will contain two non-negative space-separated integers "P" and "M", where P is the number of planets on his way back (P <= 50000) and M is the maximum number of Autobots that Megatron can see (M <= 1000,000).

After that, one line containing P integers separated by a single space will denote the number of Autobots present in each planet. (For each planet there will be no more than 1000 Autobots).

Output

Your output should consist of "T" pairs of space-separated integers, one pair per line, denoting the number of Autobots Megatron will fight and the number of planets he will destroy respectively.

Example

Input:
1
4 50
20 5 23 45

Output:
48 3

Explanation

Megatron starts at planet 1 (with 20 Autobots) and goes to planet 2, then the 3rd planet, at this point, he has seen 48 Autobots, if he decides to go to planet 4 he will see 93 Autobots... so he stops his journey at the 3rd planet.

Megatron, however, could have started at planet 2 with 5 Autobots, then continue up to the 4th planet, then, he would have seen 73 Autobots, but, as he wants to see the minimum Autobots possible and this number of Autobots exceeds what he wants to see, he decides to choose the way from the 1st to the 3rd planet.


Added by:CSI
Date:2013-09-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-06-02 11:38:33 kartikay singh
EAsy BRute FORCE B-) AC
2015-06-01 20:05:36 pingal tirkey
EASY :)
2015-02-19 18:47:24 :.Mohib.:
DOnE :)
2015-02-16 12:15:50 Daksh
nice problem :) a silly mistake give me many WA
2015-02-06 10:32:34 sameer Hussain
@sam:
I am getting correct answers for the given testcases,but failing for 5th testcase on Online Judge

Last edit: 2015-06-22 18:48:34
2014-12-29 19:41:00 Sam
If someone facing problem some test cases
2
8 10
2 34 1 2 3 4 97 99
4 3
4 4 4 4
Output
10 4
0 0
2014-12-27 11:26:07 ROHIT RAJ
nice prblm. AC in 1 go :)
2014-10-22 13:03:15 biQar
This problem should be moved into tutorial section, as there is a copy of this problem named ALIEN into the classical section.
2014-09-29 21:05:47 Ashish Sareen
Mazza Aa gaya :D
2014-09-04 12:29:39 mehrab alam
Same as problem ALIEN

Last edit: 2014-09-04 12:30:01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.