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.
Example
Input: 2 5 100 50 10 20 30 40 5 87 21 45 30 12 14 Output: Scenario #1: 90 Scenario #2: 65
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
hide comments
scolar_fuad:
20191026 11:41:20
modified 0/1 knapsake


scolar_fuad:
20190918 17:45:32
Nice variation of 0/1 knapsake easy dp ...


adist98:
20190713 23:53:42
Has anyone done it using 1D DP? Last edit: 20190713 23:53:54 

cenation007:
20190628 20:14:55
easy peasy lemon squeezy


suyashky:
20190326 14:09:25
If unable to solve this one, solve these first


faha:
20180602 21:18:32
Can anyone tell the test case restriction ?


aman_sachin200:
20180523 23:07:55
Simple 0/1 knapsack with modifications.Take care of output format...cost me 3WA:( 

nadstratosfer:
20170916 04:05:21
Bottomup DP gets TLE in Python, managed to get 0.20s AC with PyPy. Francky's time of 0.03s in raw Python implies there exists a nonDP way of solving this. Any hints? 

cichipi_:
20170609 16:37:46
take ith one recall x = fun(i+2 , lim+a[i])


don_1234:
20170401 14:03:02
Use Fast i/o in java cost me 1 tle Last edit: 20170401 14:04:24 
Added by:  david_8k 
Date:  20120412 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem used for the RPL contest 