Chia táo (Apple Division)

Nguồn: CSES Problem Set

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ quả táo với trọng lượng lần lượt là $p_1,p_2,\ldots,p_n$.

Hãy chia toàn bộ các quả táo thành hai nhóm sao cho hiệu tuyệt đối giữa tổng trọng lượng của hai nhóm là nhỏ nhất có thể.

Mỗi quả táo phải thuộc đúng một trong hai nhóm.

Input

Dòng đầu tiên chứa số nguyên $n$ — số lượng quả táo.

Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\ldots,p_n$ — trọng lượng của các quả táo.

Output

In ra một số nguyên duy nhất — hiệu tuyệt đối nhỏ nhất có thể giữa tổng trọng lượng của hai nhóm.

Subtask

• Subtask 1 — 30%: $1 \le n \le 10$; $1 \le p_i \le 10^9$.
• Subtask 2 — 70%: $1 \le n \le 20$; $1 \le p_i \le 10^9$.

Ví dụ

Input

5
3 2 7 4 1

Output

1

Giải thích

Có thể chia các quả táo thành hai nhóm:

• nhóm thứ nhất gồm các quả có trọng lượng $3,2,4$, có tổng bằng $9$;
• nhóm thứ hai gồm các quả có trọng lượng $7,1$, có tổng bằng $8$.

Hiệu tuyệt đối giữa hai tổng là

Không thể đạt được hiệu nhỏ hơn, vì vậy đáp án là 1.