Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714622

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

704. Stone Pile
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

You have a number of stones with known weights w1, …, wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones n (1 ≤ n ≤ 32) and weights of the stones w1, …, wn (integers, 1 ≤ wi ≤ 107) delimited by white spaces.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Sample

Input

Output

1

5
5 8 13 27 14
3

 

Tayyorladi: Azat Yusupov
Text from: acm.timus.ru
Mening urinishlarim(0) Muhokama (8) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(39) Barcha urinishlar(261)