Maximizing Front Section Weight

You are given a series of containers, each with a specified weight. They must be divided into two sections: a front section and a back section. The front section's total weight must not exceed the back section's total weight. In other words, if the front section has a total weight (F) and the back section has a total weight (B), then it must hold that (F \leq B). Since the sum of all container weights is (T = F + B), the condition is equivalent to (F \leq \frac{T}{2}). Your task is to select a subset of containers to load in the front section such that the sum of their weights is as large as possible without violating the condition.

Input Format: The input is read from standard input (stdin).

Example: For an input of "5\n6 3 4 2 7\n", there are 5 containers with weights 6, 3, 4, 2, and 7 respectively. A valid division yields a maximum front section weight of 11.

inputFormat

The first line of input contains a single integer (n) representing the number of containers. The second line contains (n) space-separated positive integers, each representing the weight of a container.

outputFormat

Output a single integer representing the maximum total weight that can be loaded into the front section without the front section exceeding the back section in total weight. The result is printed to standard output (stdout).## sample

5
6 3 4 2 7

11