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 i-th 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 1st blueberry bush (50), she cannot pick the 2nd, she decides not to pick until the 5th one where she picks the “40” blueberry, she could pick the 3rd bush, but she would exceed the limit (100).

Output explanation (second scenario)

Teresa picks the 1st, the 3rd and the 5th bush, total of (21+30+14 = 65) blueberries

CONSTRAINTS

1 <= N <= 1000
1 <= K <= 1000


hide comments
adist98: 2019-07-13 23:53:42

Has anyone done it using 1-D DP?

Last edit: 2019-07-13 23:53:54
cenation007: 2019-06-28 20:14:55

easy peasy lemon squeezy
Ac in one go :)

suyashky: 2019-03-26 14:09:25

If unable to solve this one, solve these first

1 The Knapsack Problem ( https://www.spoj.com/problems/KNAPSACK/ )
2 Save Thy Toys ( https://www.spoj.com/problems/DCEPC501/ )

faha: 2018-06-02 21:18:32

Can anyone tell the test case restriction ?

aman_sachin200: 2018-05-23 23:07:55

Simple 0/1 knapsack with modifications.Take care of output format...cost me 3WA:(

nadstratosfer: 2017-09-16 04:05:21

Bottom-up 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 non-DP way of solving this. Any hints?

cichipi_: 2017-06-09 16:37:46

take ith one recall x = fun(i+2 , lim+a[i])
don't take ith one, y = fun(i+1 , lim)
return the max of them
it will get TLE....as it computing same state once more
so , we take dp[1007][1007] = -1 all
inside the function if dp[i][limit]!=-1 then we need not copute it again....we just return dp[i][lim]
finally return dp[i][limit] = max(x,y);

Last edit: 2017-06-09 16:40:25
don_1234: 2017-04-01 14:03:02

Use Fast i/o in java cost me 1 tle

Last edit: 2017-04-01 14:04:24
manas0008: 2017-02-05 07:12:38

Start afresh
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

and realise it's no more than knapsack at the end.

mkfeuhrer: 2017-02-02 22:05:47

its just 0 - 1 knapsack ! ! dont thnk much :-P . check print format !!


Added by:david_8k
Date:2012-04-12
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