An sống ở một vùng quê yên bình, mỗi dịp Tết đến gia đình An thường gói ghém rất nhiều phần quà để chia cho hai họ hàng nội ngoại. Năm nay, mẹ An chuẩn bị \(N\) hộp kẹo, hộp thứ \(i\) có khối lượng \(a_i\) (đơn vị gam). An muốn chia toàn bộ \(N\) hộp kẹo thành đúng hai nhóm (một nhóm cho họ nội, một nhóm cho họ ngoại) sao cho chênh lệch khối lượng giữa hai nhóm là nhỏ nhất có thể. Hãy giúp An tìm con số chênh lệch nhỏ nhất đó.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 20\)).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 10^3\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là chênh lệch khối lượng nhỏ nhất giữa hai nhóm.

Ví dụ

Input:

4
1 2 3 4

Output:

0

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 10\).
• \(30\%\) số điểm ứng với \(N \le 15\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.