Two-Pan Balance

You are given a set of weights with distinct masses. Each weight has an integer mass from 1g to 9g. You may choose some of these weights and place them on a two-pan balance so that the balance is level.

Each side of the balance has five equally spaced marks from the center. A weight may be placed only on a mark, and at most one weight may be placed on each mark. For example, if the set of weights is {2, 3, 4, 5, 9}, placing the 2g weight on the left at distance 3 from the center and the 3g weight on the right at distance 2 balances the scale because 2×3 = 3×2. With the same set, placing the 4g weight at left distance 4, the 2g weight at left distance 2, and the 5g weight at right distance 4 also balances it because 4×4 + 2×2 = 5×4.

For each balanced arrangement, create one number as follows. Read the ten marks from the far left to the far right. Write 0 for an empty mark, and write the weight mass for an occupied mark. Then remove all leading zeros before the first nonzero digit. The first arrangement above corresponds to 20003000, and the second corresponds to 402000050. The resulting integer, which has at most 10 digits, is called a balanced integer.

Given the set of weights, list all balanced integers that can be made in increasing order and print the one with rank k. Here 0 ≤ k ≤ 1,000,000,000, and the balanced integer for k = 0 is 0, representing the arrangement with no weights on either side. If no balanced integer has rank k, print the largest balanced integer that can be made.

The first line contains the size n of the weight set. 1 ≤ n ≤ 9.

The second line contains n distinct weights in increasing order. Each weight is an integer from 1 to 9, and adjacent values are separated by one space.

The third line contains the rank k to compute.

Print the balanced integer with rank k among all balanced integers that can be made from the given weights, listed in increasing order. If no such integer exists, print the largest balanced integer that can be made.