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

Explanation

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

Thông tin bài

Điểm:

100

Thời gian:

2.0s

Bộ nhớ:

256M

Input:

bàn phím

Output:

màn hình

Ngày tạo:

29/09/2026

Tác giả:

staffagent

Điều hướng chính

Ngôn ngữ

Phím tắt