ALIEN  Aliens at the train
The aliens have arrived to Earth and everything is in harmony, the two races can live together. However, one specific Female Alien does not want to see humans on her way to the university, the alien must use the train as every human does. But she can choose any train station such she doesn’t see more than B humans, however, the Alien wants to go as far as possible with the train. Please, help her in this task.
Input
You will receive one integer T denoting the number of test cases, then, the next line will contain two integers At Bt where At and Bt is the number of stations in the train (1 <= At <= 100,000) and the number of people that the alien wants to see as maximum (1 <= Bt <= 10,000,000), after that, one line containing At integers separated by a single space will denote the number of people the Alien can find in the Atith station. (For each station there will be as much 100 people)
Output
Your output should consist on T pair of numbers denoting the number of people the alien will see and the number of stations she will pass respectively.
Example
INPUT: 1 5 100 20 15 30 80 100 OUTPUT 65 3
Output note:
The alien takes the train at station 1 (with 20 people) and goes to station 2, then the 3rd station, at this point, she have seen 65 people, if she decides to go to station 4 she will see 145 people… Then she exits the station.
The alien, however, can start at station 2 with 15 people, then continue up to the 4th station, then, she would have seen 125 people, but, as she wants to see the minimum people possible and this number of people exceeds what she wants to see, she decides to choose the way from the 1st to the 3rd station.
Clarification: The alien will be moving always forward (remember, she can choose any station as a start), NEVER backwards, and you should choose the best path that satisfies the output specification.
hide comments
akibk001:
20190417 21:57:47
@admin add this test case


sai_chavali:
20190309 13:55:30
python solution is giving TLE. Does anyone have any idea? 

nobody550:
20190226 14:42:56
Can be solved using prefix array and binary search, try this as well


aks473:
20190208 21:03:54
Try this:


ameyanator:
20180924 07:35:15
Problem statement not very clear. When 2 pairs where the distance between them is same choose the one with minimum number of humans in them


one_piece_:
20180629 06:57:06
remember she does not like human, even if path length is same Last edit: 20180629 06:58:45 

vivek_dwivedi:
20180622 20:09:48
getting WA // read last line of clarification carefully. chhers


anirudnits:
20180604 18:14:57
binary search also works. Last edit: 20180604 18:15:11 

lazyfellow:
20180107 07:49:09
@ppspj_066 that forgetfulness cost me 2 WA 

biswajitk123:
20171220 19:18:04
@ppsj_066 that remember saved my life

Added by:  david_8k 
Date:  20120114 
Time limit:  0.159s0.333s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 