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 nonnegative spaceseparated 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 spaceseparated 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.
hide comments
Jumpy:
20190421 19:42:34
Strage thing happened. Got AC in nlog(n) approach with 0.13 sec. Whereas, when it used fast I/O optimization adding these two lines, I am getting WA. Requesting author to check why it is so.


mag1x_:
20180623 20:49:27
when corner cases hunt you :3 

babur:
20170624 09:12:06
COPY PASTE.....TIME WASTE 

karan_batra:
20160911 18:45:49
Same as ALIEN _ 

krototype:
20160724 09:13:40
Exactly same problem as ALIENS.....O(n) approach


dwij28:
20160627 11:21:24
Just one thing to take care of: In case there are more than one such solution where maximum number of planets is same, choose the one the with less total number of autobots. Classical Two Pointer Problem. :) 

mkfeuhrer:
20160621 22:32:55
copy paste ALIENS :P 

iamstg:
20160501 22:08:49
Seems like this problem has comparitively stronger test cases than aliens problem coz the code which got accepted in aliens did'nt get AC here unless some modifications were done 

gulshan_raj:
20151120 16:01:04
@admin same as alien 

Mayank Garg:
20150927 17:04:40
Easy one :) nice way to get 200th green !! :) 
Added by:  CSI 
Date:  20130930 
Time limit:  0.167s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 