{"code":"demen04","name":"Nuôi Bò 2","description":"Sau một thời gian chuyển sang nuôi bò lấy sữa [user:DeMen100ms] thu được lợi nhuận rất tốt. [user:DeMen100ms] muốn chuyển giao đàn bò này cho hai con của mình tiếp tục nuôi.\r\n\r\nĐàn bò của [user:DeMen100ms] có $n$ con bò, con thứ $i$ có trọng lượng $a_i$. Bây giờ [user:DeMen100ms] muốn chia bò thành hai phần để cho hai con của mình. [user: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 [user:DeMen100ms] liệu chênh lệch hai phần này nhỏ nhất là bao nhiêu.\r\n\r\n

Input

\r\n\r\n- Dòng thứ nhất là hai số nguyên dương $n (1 \\le n \\le 38)$\r\n\r\n- 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).$\r\n\r\n

Output

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 5\r\n 13 5 1 5 20\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2\r\n ```","points":300.0,"partial":false,"time_limit":1.5,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}