마법사 리안은 \(N\) 개의 마법 룬을 가지고 있다. \(i\) 번째 룬의 무게는 \(w_i\) 이다. 리안은 이 룬들을 두 개의 더미로 나누어 마법진의 양쪽 받침대에 올려 두려고 한다. 받침대가 한쪽으로 기울면 마법진이 불안정해지므로, 두 더미의 무게 차이의 절댓값을 가능한 한 작게 만들고 싶다.

모든 룬은 반드시 두 더미 중 정확히 한 곳에 속해야 한다. 한쪽 더미가 비어 있어도 (모든 룬을 한 더미에 몰아도) 무방하다.

각 룬을 어느 더미에 넣을지 자유롭게 정할 수 있을 때, 두 더미의 무게 차이의 최솟값을 구하라.

예를 들어 룬의 무게가 \(4, 1, 7, 2\) 라면 \(\{7\}\) 과 \(\{4, 1, 2\}\) 로 나누어 양쪽 무게를 모두 \(7\) 로 만들 수 있으므로 차이의 최솟값은 \(0\) 이다.

\(N\) 이 최대 \(40\) 까지 커질 수 있으므로, 단순히 모든 부분집합을 (\(2^{40}\) 가지) 열거하는 방법은 시간 안에 끝나지 않는다는 점에 유의하라.

\(1 \le N \le 40\)

\(1 \le w_i \le 10^{12}\)

첫째 줄에 룬의 개수 \(N\) 이 주어진다.

둘째 줄에 \(N\) 개의 정수 \(w_1, w_2, \dots, w_N\) 이 공백으로 구분되어 주어진다.

두 더미의 무게 차이의 절댓값이 가질 수 있는 최솟값을 한 줄에 출력한다.

riseoj 작성

출처 Original