Chia trâu đều nhau

Chủ trại có \(N\) con trâu, con thứ \(i\) nặng \(w_i\). Ông chọn ra một số con trong đàn (có thể không phải tất cả) rồi chia số con được chọn thành đúng hai nhóm không giao nhau sao cho tổng cân nặng hai nhóm bằng nhau. Hãy tìm tổng cân nặng lớn nhất của mỗi nhóm có thể đạt được. Nếu không thể chia được với cả hai nhóm khác rỗng thì in \(0\).

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên \(w_1, \dots, w_N\).

Output

• In ra tổng cân nặng lớn nhất của một nhóm.

Constraints

• \(1 \le N \le 22\)
• \(1 \le w_i \le 10^9\)

Sample Input

5
3 3 6 2 4

Sample Output

9

Explanation

Nhóm 1: \(\{3, 6\}\), nhóm 2: \(\{3, 2, 4\}\), mỗi nhóm nặng 9.