Мечето Ушко и зајачето Долгоушко се едни од најверните поданици на Кралот Лав, па тој решил да ги награди за нивната верна служба. Бидејќи Ушко и Долгоушко се големи љубители на музика, Кралот Лав одлучил да им подари N DVD-ја со најголемите хитови. Секое DVD содржи одреден број на песни - првото содржи R[1] песни, второто R[2] песни, итн.

За да се избегнат можни кавги, Кралот му заповедал на својот слуга, магаренцето Доне, да ги подели DVD-јата на фер начин така што разликата помеѓу бројот на песни кои ќе ги добие мечето Ушко и бројот на песни кои ќе ги добие зајачето Долгоушко да биде минимална.

Магаренцето Доне не е најинтелигентно и не може да се снајде со оваа задача, затоа ве моли за помош! Напишете програма која ќе го подели множеството DVD-ја на две подмножества така што ако P е бројот на песни во првото подмножество DVD-ја, а Q e бројот на песни во второто подмножество DVD-ја, разликата помеѓу P и Q ќе биде што е можно помала.

Влез

Во првата линија е даден еден цел позитивен број N (2 ≤ N ≤ 300), кој го претставува бројот на DVD-ја.

Во втората линија се дадени N цели позитивни броеви R[i], одвоени со празно место, кои го претставуваат бројот на песни на секое DVD, соодветно. Притоа важи R[1] + R[2] + ... + R[N] ≤ 100 000.

Забелешка: Во тест случаи кои вредат најмалку 50% од поените, важи 2 ≤ N ≤ 20.

Излез

Првата и единствена линија од стандардниот излез треба да ја содржи апсолутната разлика помеѓу вкупниот број на песни во двете подмножества - поделени на фер начин.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5
1 9 5 3 8

излез
0

влез
2
3 8

излез
5

Објаснување за првиот тест пример: оптималната поделба на DVD-јата ќе биде на подмножества (1, 9, 3) со вкупен број песни 13 и (5, 8) со вкупен број песни 5+8=13, па бараната апсолутна разлика е 13-13=0.