Chia Táo Thành Hai Nhóm

Có $n$ quả táo với trọng lượng đã biết. Hãy chia toàn bộ táo thành hai nhóm sao cho chênh lệch giữa tổng trọng lượng hai nhóm là nhỏ nhất.

Input

• Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$.

Output

• In chênh lệch nhỏ nhất có thể đạt được.

Constraints

• $1\le n\le 20$.
• $1\le p_i\le 10^9$.
• Mỗi quả táo thuộc đúng một trong hai nhóm; một nhóm có thể rỗng.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 10$ và $p_i\le 1000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5
3 2 7 4 1

1