Nam và Việt cùng hợp tác thực hiện một dự án kinh doanh. Khi dự án kết thúc, tài sản còn lại gồm \(n\) vật dụng, vật dụng thứ \(i\) \((i = 1, 2, \ldots, n)\) có giá trị là \(c_i\).

Hai người cần chia các vật dụng thành hai phần để sở hữu riêng sao cho tổng giá trị của hai phần bằng nhau. Do mỗi vật dụng là nguyên khối và không thể tách nhỏ, nên không phải lúc nào cũng có thể sử dụng toàn bộ vật dụng để thực hiện cách phân chia này.

Sau khi chia các vật dụng thành hai phần có tổng giá trị bằng nhau và lớn nhất. Các vật dụng còn lại (nếu có) được bán cho đại lý để nhận phiếu mua hàng có giá trị bằng hai lần tổng giá trị của chúng. Giá trị phiếu mua hàng được chia đều và cộng vào tổng tài sản của mỗi người.

Yêu cầu: Cho giá trị của \(n\) vật dụng ban đầu, hãy xác định tổng giá trị cuối cùng mỗi người nhận được.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương \(n\) \((n \le 500)\) là số lượng vật dụng;
• \(n\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(c_i\) \((c_i \le 10^5)\) là giá trị của vật dụng thứ \(i\).

Dữ liệu vào bảo đảm \(\displaystyle\sum_{i=1}^{n} c_i \le 10^5\).

Kết quả:

• Một số nguyên duy nhất là tổng giá trị mà mỗi người nhận được.

Ví dụ:

Dữ liệu vào

5
2
3
5
8
13

Kết quả

18

Giải thích: Có thể chia các vật dụng thành hai phần {5, 8} và {13}, mỗi phần có tổng giá trị bằng 13, đây là tổng giá trị lớn nhất có thể đạt được. Các vật dụng còn lại là {2, 3}, có tổng giá trị là 5, được bán lại để nhận phiếu mua hàng có giá trị 10. Giá trị phiếu mua hàng được chia đều, mỗi người nhận thêm 5. Do đó, tổng giá trị cuối cùng mỗi người nhận được là \(13 + 5 = 18\).

Ràng buộc:

• Subtask 1 (50% số điểm): \(n \le 13\);
• Subtask 2 (30% số điểm): \(n \le 50\); tổng giá trị vật dụng không vượt quá 1000;
• Subtask 3 (20% số điểm): Không ràng buộc gì thêm.