Bố của hai anh em Bắc và Giang vừa có một chuyến đi làm ăn xa về. Ông đã chuẩn bị N gối quà, các gói quà được đánh số từ 1 đến N, gói quà thứ i có giá trị là c_i. Ông sẽ chia hết số quà cho hai anh em Bắc và Giang vì hai anh em đã động viên ông trong suốt quãng thời gian ông đi làm. Ông chia quá thành hai phần với tổng giá trị của từng phần là S1 và S2, độ chênh lệch giữa hai phần quả là giá trị tuyệt đối của S1-S2, và mỗi anh em sẽ nhận một trong hai phần quà đó

Yêu cầu: Giúp bố của Bắc và Giang chia quà cho hai anh em sao cho độ chênh lệch giữa hai phần quá là nhỏ nhất.

Ví dụ:

Input	Output
3 1 3 1	1

(Đề thi tin học trẻ tỉnh Bắc Giang 2019 – Bảng C – THPT)

•   Điểm: 100
•   Time limit: 1.0s
•   Loại đề bài: C++, Python