Є ~n~ яблук з відомою вагою.

Ваше завдання — розділити яблука на дві групи так, щоб різниця між вагою груп була мінімальною.

Обмеження

• ~1 \le n \le 20~
• ~1 \le p_i \le 10^9~

Формат вхідних даних

Перший рядок містить ціле число ~n~: кількість яблук.

Наступний рядок містить ~n~ цілих чисел ~p_1,p_2,\dots,p_n~: вага кожного яблука.

Формат вихідних даних

Виведіть одне ціле число: мінімальну різницю між вагами груп.

Приклад вхідних даних

5
3 2 7 4 1

Приклад вихідних даних

1

Пояснення

група 1 має ваги 2, 3 і 4 (загальна вага 9), а група 2 має ваги 1 і 7 (загальна вага 8).