RPLB  Blueberries
Teresa picked up enough strawberries, now she wants to pick blueberries from the magical blueberry bush from Rainbowland.
Knowing her previous experience with the strawberries, Teresa wants to pick up the blueberries in a way that she may not exceed the limit proposed.
When picking the blueberries, she noticed that if she pick from the bush i, she couldn't pick the blueberries at the bush i+1 (some sort of magic in rainbowland).
Worried about this, Teresa wants to know the maximum blueberries she can pick, given the number of bushes and the number of blueberries in each bush.
INPUT:
Will contain an integer T, then, T cases will follow, each case starts with a number N and K, being N the number of bushes and K the number of blueberries Teresa will pick as maximum, the next line contains N integers, each one representing the blueberries there is on the ith bush.
OUTPUT:
You will output for each test case the string: “Scenario #i: “ where i is the test case you are analyzing, then, an integer denoting the maximum number of blueberries you can grab.
INPUT 
OUTPUT 
2 5 100 50 10 20 30 40
5 87 21 45 30 12 14 
Scenario #1: 90 Scenario #2: 65 
“Blank line between test cases for clarification and separation”
Output explanation (first scenario)
Teresa picks the 1^{st} blueberry bush (50), she cannot pick the 2^{nd}, she decides not to pick until the 5^{th} one where she picks the “40” blueberry, she could pick the 3^{rd} bush, but she would exceed the limit (100).
Output explanation (second scenario)
Teresa picks the 1^{st}, the 3^{rd} and the 5^{th} bush, total of (21+30+14 = 65) blueberries
CONSTRAINTS:
1<=N<=1000; 1<=K<=1000
Added by:  david_8k 
Date:  20120412 
Time limit:  0.439s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All 
Resource:  Own Problem used for the RPL contest 
hide comments
Mayank Garg:
20150819 19:27:09
At last accepted .. silly mistake costed me a WA :p my 150th !! Easy dp !! :) 

harshit sharma:
20150722 18:03:15
good dp....easy 1 :) 

Shashank Tiwari:
20150710 11:16:39
Okay , if you are getting wrong answer , then check ...


thewatch:
20150610 22:05:05
Nice Problem!! My 100th!! 

AlphaDecay:
20150609 16:35:00
Nice One ! 

Shashank Gupta:
20150409 03:36:22
Nice problem ... Think DP :D 

freaker:
20141215 16:15:24
nice DP problem for beginners like me ... Last edit: 20141215 16:18:53 

Rohan Jain:
20141206 19:51:26
knapsack..:D 

AlcatraZ:
20140830 21:30:56
Good problem .. Take care of output format though. 

Shantanu Singh:
20140701 13:06:44
At last phew... My first DP :D ..Took a lot of time but finally got it correct ;) 