Taco Task Scheduling

You are given a set of tasks, each with a positive integer indicating the time needed for its completion. The goal is to schedule these tasks on two computers such that the overall time to finish all tasks is minimized. The tasks are processed in parallel (one per computer), and the completion time is determined by the computer that finishes last.

This problem is analogous to partitioning the task set into two subsets so that the maximum of the sums of the times in each subset is as small as possible. Formally, if \(T\) is the total sum of all task times and \(S\) is the sum of tasks assigned to one computer, then the minimum total time required is \(\max(S, T-S)\).

inputFormat

The first line contains an integer (n) ((1 \leq n \leq 1000)), the number of tasks. The second line contains (n) space-separated integers (a_1, a_2, \ldots, a_n) where each (a_i) ((1 \leq a_i \leq 1000)) indicates the time required for task (i).

outputFormat

Print a single integer representing the minimum total time required to complete all tasks using the two computers concurrently.## sample

5
2 2 3 3 4

7