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 At-i-th 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
Francis: 2014-04-10 09:35:31

God,this simple prob costs me 4 TLE and 3 WA. I first used a simple alg with O(n^2) in python and got 3 TLE. Then I changed into sliding window alg with C and got 3 WA because I was not totally clear about the process. Finally I cleaned my head and got AC in C with 1.91s in C and TLE in python(SAME alg).
My final code is here(Removed) with some test cases from forum below, can ANYONE tell me how to improve my code(1.91s is too much)???
I noticed there is someone who used 2.33s in C and got AC while the timelimit is 1s-2s, how could that happen?
Any advice on this prob is welcome for me. Thx very much in advance! :)
@.::Lakshman::. Thx anyway.::Lakshman::.! Do you mean every user's AC time is decided by a same file contains all test cases??? If so, what do you mean by using fast I/O to optimize code??? I really have no idea how to improve my C code by fast I/O efficiently actually. Can you give me some specific demos? Thx in advance!:)
@.::Lakshman::. Thx so much.::Lakshman::.! I am just online and I have deleted my code link! You can delete your link now. The C code after your improvement gets 0.25s, that is really cool. I really appreciate your sharing. :):):)

Last edit: 2014-04-10 18:13:37

Added by:david_8k
Date:2012-01-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem