Sau một thời gian chuyển sang nuôi bò lấy sữa DeMen100ms thu được lợi nhuận rất tốt. DeMen100ms muốn chuyển giao đàn bò này cho hai con của mình tiếp tục nuôi.

Đàn bò của DeMen100ms có \(n\) con bò, con thứ \(i\) có trọng lượng \(a_i\). Bây giờ DeMen100ms muốn chia bò thành hai phần để cho hai con của mình. DeMen100ms muốn chia sao cho sự chênh lệch về tổng trọng lượng bò của hai phần là ít nhất có thể. Bạn hãy tính giúp cho DeMen100ms liệu chênh lệch hai phần này nhỏ nhất là bao nhiêu.

Input

• Dòng thứ nhất là hai số nguyên dương \(n (1 \le n \le 38)\)

• Dòng thứ hai là là \(n\) số nguyên dương \(a_1, a_2, ... a_n (1 \le a_i \le 10^9).\)

Output

• In ra một số nguyên duy nhất là chênh lệch bé nhất của hai tập bò.

Example

5
13 5 1 5 20

2