Unequalled Consumption

Time limit1sMemory limit128 MB

Summary

Given up to 5 candy weights, find for each query P the smallest total weight whose number of representations (as an unordered multiset count) is at least P, using binary search over weight combined with counting compositions via generating functions or DP.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Math, Combinatorics
Solved: No attempts yet

Problem

The Association of Candy Makers is preparing to launch a new product. The idea is old with a novel twist: it simply sells boxes of candies. But since people are what they consume and everyone wants to be unique these days, the Association wants every candy box to be unique, in the sense that no two boxes contain the same composition of candy types.

The Association can make only a small number $n$ of different candy types, and though limited in imagination, it is virtually limitless in resources, so it can produce as many of each type as it wants. The candy types have weights (some types may weigh the same), and to simplify pricing the Association wants every candy box to have the same total weight.

With these restrictions, the Association can make only a limited number of boxes. For instance, with three candy types weighing $5$ , $5$ , and $10$ grams, $4$ different boxes can be made with total weight $10$ grams: two of type 1, or two of type 2, or one of type 3, or one each of types 1 and 2. The Association would like to make at least one box for everyone in the cosmos. Given the number of people $P$ in the cosmos, find the smallest possible total weight $w$ such that $P$ different boxes containing exactly $w$ grams of candy can be made.

Input

The input contains several data sets (at most $20$ ). Each data set is given on four lines:

The first line contains an integer $n$ ( $1 \le n \le 5$ ), the number of candy types.
The second line contains $n$ integers $w_1, \dots, w_n$ ( $1 \le w_i \le 10$ ), the weight in grams of each type.
The third line contains an integer $q$ ( $1 \le q \le 10$ ), the number of queries.
The fourth line contains $q$ integers $P_1, \dots, P_q$ ( $1 \le P_j \le 10^{15}$ ), the queries.

The input ends with a line containing a single $0$ in place of $n$ ; that terminating data set must not be processed.

Output

For the $i$ -th data set, print a line Set i, then one line per query. For query $P_j$ , print the smallest positive weight $W_j$ (in grams) for which at least $P_j$ different boxes of total weight exactly $W_j$ grams exist. If there is no such weight, print no candy for you for that query instead. When a weight exists, it is at most $100 \cdot P_j$ .

Examples3

Example 1

Input

Expected output

Set 1
10
Set 2
23
42
Set 3
no candy for you

Example 2
Input
```
1
7
2
1 2
0
```
Expected output
```
Set 1
7
no candy for you
```

Example 3

Input

Expected output