Đọc Sách

Có $n$ quyển sách, sách thứ $i$ cần $t_i$ giây để đọc. Hai người cần đọc hết tất cả các sách, mỗi người phải đọc từng quyển từ đầu đến cuối. Hai người không được đọc cùng một quyển sách cùng lúc nhưng có thể đọc các sách khác nhau đồng thời. Hãy tính thời gian tối thiểu để cả hai hoàn thành tất cả sách.

Dữ liệu vào

• Dòng 1: số nguyên $n$.
• Dòng 2: $n$ số nguyên $t_1,t_2,\dots ,t_n$.

Dữ liệu ra

In một số nguyên — thời gian tối thiểu.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le t_i\le {10}^9$

Ví dụ