Sau khi giải xong câu đố, Alice và Bob đã mở được kho báu. Kho báu gồm \(n\) vật, cả hai quyết định phân chia các vật lấy được theo nguyên tắc sau:

• Bước 1: Cả hai cùng nhau ước giá \(n\) vật, vật thứ \(i\) (\(1 \le i \le n\)) được ước giá là \(v_i\).
• Bước 2: Chọn một số vật, phân chia các vật đã chọn thành hai phần mà tổng ước giá của hai phần là bằng nhau, mỗi người nhận một phần.
• Bước 3: Các vật còn lại sẽ đem bán rồi chia đều cho cả hai. Để hạn chế phải bán các vật, Alice và Bob thống nhất tổng ước giá các vật đem bán là nhỏ nhất.

Yêu cầu: Cho \(v_1, v_2, \dots, v_n\) là ước giá của \(n\) vật, hãy đưa ra tổng ước giá các vật đem bán nhỏ nhất.

Input

Dữ liệu vào từ thiết bị vào chuẩn gồm nhiều bộ dữ liệu, mỗi bộ có khuôn dạng sau:

• Dòng đầu chứa số nguyên \(n\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(v_i\).

Output

• Ghi ra thiết bị ra chuẩn gồm nhiều dòng, mỗi dòng chứa một số nguyên là tổng ước giá các vật đem bán nhỏ nhất tìm được tương ứng với dữ liệu vào.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 12; v_i \le 10^9\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 24; v_i \le 10^9\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 48; v_i \le 10^2\).
• Subtask \(4\) (\(30\%\) số điểm): \(n \le 96; v_i \le 10^3\).

Example

3
1
2
3
4
2
2
4
1

0
1