Dr. Henri is a very busy person. He has responsibilities to attend to over the next two days. Being a very organized person, he wants to split the tasks evenly between the two days. More specifically, if the tasks on day 1 take seconds, and the tasks on day 2 take seconds, he wants to minimize the value of .
The task takes him seconds, and must be completed within a single day. Dr. Henri, being very busy with these tasks, then asks you: what is the minimum value of if he partitions his tasks optimally?
Subtask 1 [20%]
Subtask 2 [80%]
The first line of input will contain an single integer, . The next and final line of input will contain space separated integers:
Output the minimum value of if Dr. Henri partitions the tasks optimally.
6 4 2 3 1 1 1
Explanation for Sample Input
If he partitions the task as and , they both sum to , and thus the difference is .