Loadout Budget Nearest Match

You are assembling a character loadout for a game. There are several base gear sets, and you must equip exactly one of them. There are also several kinds of upgrade gem; for each kind you may attach it zero, one, or two times to the equipped gear set (never more than two of the same kind, and any subset of kinds may be skipped entirely). Given a target budget, choose one base gear set and a count of 0, 1, or 2 for each gem kind so that the total cost of the loadout is as close as possible to the target. If two different achievable totals are equally close to the target, report the smaller total.

Input format

• Line 1: an integer n — the number of base gear sets (1 <= n <= 10).
• Line 2: n integers — the cost of each base gear set (1 <= cost <= 10^4).
• Line 3: an integer m — the number of upgrade gem kinds (1 <= m <= 10).
• Line 4: m integers — the cost of a single copy of each gem kind (1 <= cost <= 1000).
• Line 5: an integer target — the target budget (1 <= target <= 10^4).

Output format

Print a single integer: the achievable total cost (one base gear set plus 0, 1, or 2 copies of each gem kind) that is closest to target. If two achievable totals are equally close to target, print the smaller one.

Constraints

• 1 <= n, m <= 10
• 1 <= base gear set cost <= 10^4
• 1 <= gem kind cost <= 1000
• 1 <= target <= 10^4

2
50 70
2
30 40
100

100

2
20 30
3
40 50 1000
180

170