Chia trâu cho hai con

Chủ trại có \(N\) con trâu, con thứ \(i\) nặng \(w_i\). Ông muốn chia toàn bộ đàn thành hai nhóm (một nhóm có thể rỗng) sao cho chênh lệch giữa tổng cân nặng của hai nhóm là nhỏ nhất. Hãy tìm chênh lệch nhỏ nhất đó.

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên \(w_1, \dots, w_N\).

Output

• In ra chênh lệch nhỏ nhất (là một số không âm).

Constraints

• \(1 \le N \le 38\)
• \(1 \le w_i \le 10^9\)

Sample Input

6
8 3 5 9 2 6

Sample Output

1

Explanation

Tổng là \(33\); chia thành \(\{8,9\}\) (17) và \(\{3,5,2,6\}\) (16), chênh lệch 1.