Hai máy đọc chung kho tài liệu

Bối cảnh và bài toán

Hai máy A và B đều phải xử lý toàn bộ n tài liệu. Một tài liệu mất t[i] thời gian trên mỗi máy. Hai máy có thể xử lý hai tài liệu khác nhau song song, nhưng cùng một tài liệu không thể được hai máy xử lý đồng thời. Mỗi máy phải xử lý mỗi tài liệu đúng một lần.

Yêu cầu

Tìm thời gian nhỏ nhất để cả hai máy hoàn tất toàn bộ tài liệu.

Input

• Dòng 1: n.
• Dòng 2: n thời gian t[i].

Output

In thời gian tối thiểu.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= t[i] <= 10^9

Chấm điểm

Ví dụ 1

Input

3
2 8 3

Output

16

Giải thích. Tài liệu dài nhất 8 tạo lower bound 16; có thể sắp lịch đạt đúng 16.

Ví dụ 2

Input

1
5

Output

10

Giải thích. Hai máy phải xử lý cùng tài liệu lần lượt, tổng 10.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Reading Books (Task 1631).

Tham khảo: https://cses.fi/problemset/task/1631