本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1260. I. Shopping Spree


Description

You've won a shopping spree with a very peculiar rule. The items you are allowed to take are in consecutive order, indexed 1 through n. You may select any subset of these items subject to the following constraint:
For each index k of items chosen for the subset
          at most half of the items with indexes 1 through k may be in the subset
For example, if the item with index 10 is chosen for the subset, then your selected subset can contain at most half of the items with index 1 through 10. Similarly, if the item with index 2 is chosen for the subset, then your selected subset can contain at most half of the items with index 1 through 2. Note that “half” is an integer value so half of 10 and 11 are both 5. The only exception to the constraint is that if the item with index 1 is chosen for the subset, you can select 1 item and not zero (to be fair).


The Problem:


Given a list of the dollar values of items, I1, I2, … In, in the shopping spree, determine the maximum value you can obtain from the shopping spree subject to the above constraint.


Input

The first line of the input is a positive integer, n, indicating the number of shopping sprees that your program will have to analyze. Following this will be the descriptions of each shopping spree. Each shopping spree will be described on a single line. The first value on each of these lines will be a single positive integer, s (s ≤ 500), representing the number of items for the shopping spree. The next s space-separated positive integers will be the values for the shopping spree items in dollars, in order. Each of these values will be less than or equal to 106.

Output

For each shopping spree, first output the heading “Spree #d: ”, where d is the spree number, starting with 1. Then, print a single integer equal to the maximum value, in dollars, that can be obtained for that shopping spree. Follow the format illustrated in Sample Output.

Samples

Input Copy
2
5
1 2 3 4 5
3
12 2 4
Output
Spree #1: 9
Spree #2: 12

Source

UCF2014
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1029. UCF 2014
My history solutions

You didn't submit any solution!
Submit your solution

Login Register