Tên bài: Đọc sách cùng nhau

Mô tả bài toán

Có ~ n ~ cuốn sách, và cả hai người bạn Tý và Tèo muốn đọc hết tất cả. Mỗi cuốn sách ~ i ~ mất ~ t_i ~ phút để đọc. Cả hai người có thể đọc đồng thời nhưng không thể đọc cùng một cuốn sách tại cùng một thời điểm.

Hai người đều đọc từ đầu đến cuối cuốn sách mà họ chọn. Nhiệm vụ của bạn là tìm tổng thời gian tối thiểu để cả hai đều đọc hết tất cả sách.

Input Format:

• Dòng đầu tiên chứa số nguyên ~ n ~: số lượng sách.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ t_1, t_2, \dots, t_n ~: thời gian cần thiết để đọc mỗi cuốn sách.

Output Format:

• In ra một số nguyên: tổng thời gian tối thiểu.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq t_i \leq 10^9 ~

Ví dụ

Input:

3
2 8 3

Output:

16

Giải thích:

• Phân chia công việc tối ưu:
  • Tý đọc quyển 1 và 3 hết: ~ [2] và [3] ~, tổng thời gian = ~ 2 + 3 = 5 ~.
  • Tèo đọc quyển 2: ~ [8] ~, tổng thời gian = ~ 8 ~.
  • Vì yêu cầu cả 2 phải đọc hết các sách nên tổng thời gian tối thiểu để hoàn thành là ~ 16 ~.