Helene's Mushroom Soup: Find the Closest Container Volume

Helene the Husky Chef is preparing her famous mushroom soup recipe. To achieve the perfect recipe, she needs a specific target volume \(T\) of mushrooms (in liters). She has a collection of containers, each containing a different volume of mushrooms. Helene wants to choose a combination of these containers so that their total volume is as close as possible to \(T\). If there are two combinations with the same absolute difference from \(T\), she will choose the one with the greater total volume.

Your task is to write a program that, given the target volume and the volumes of available containers, finds the combined volume of containers that is closest to \(T\) according to the rule described above.

Note: The input is given via standard input (stdin) and the result must be output to standard output (stdout).

inputFormat

The input consists of two lines:

• The first line contains an integer \(T\) representing the target volume.
• The second line contains space-separated integers representing the volumes of the available containers.

It is guaranteed that at least one container is provided.

outputFormat

Output a single integer representing the combined volume of the selected containers which is the closest to \(T\). If two totals are equally close, output the greater one.

1500
500 600 700 800 300

1500