文理学院程序设计在线练习


Stone pile

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 134   Accepted Submission(s): 64
Problem Description

You have a number of stones with known weights W1, …, Wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones N (1 ≤ N ≤ 20) and weights of the stones W1, …, Wn (1 ≤ Wi ≤ 100000) delimited by white spaces. Process to the end of file.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Sample Input
5
5 8 13 27 14 
13
2228 20462 4902 8508 18542 5224 2550 588 7673 19923 17106 28324 16756 
3
23488 25647 25327
Sample Output
3
22
23168
Source

USU Championship 1997