В столице королевства Бубея Второго построен новый мост, который решено украсить статуями работы лучших мастеров. Для украшения моста были выбраны \textbf{N} мастеров, каждый из которых создал по одной статуе. К сожалению, мастера сделали статуи разного веса, поэтому если эти произведения искусства распределить между левой и правой сторонами моста произвольным образом, то возникнет риск, что одна из сторон "перетянет" и мост опрокинется. С другой стороны, проект уже утверждён Его Величеством и необходимо обязательно использовать все статуи. Определите оптимальное распределение статуй между левой и правой сторонами моста. \InputFile Сначала вводится число \textbf{N} (натуральное, не превышает \textbf{12}), затем вводятся \textbf{N} чисел (натуральные, не превышают\textbf{1000}) - веса статуй. \OutputFile Выведите единственное число - наименьшую возможную разницу в суммарном весе статуй на левой и правой сторонах моста. На каждой стороне может стоять любое количество статуй.