THỰC HÀNH

Đề nghị bạn hãy viết chương trình tính toán với đề bài liên quan đến tin học.

Máy tính hiện tại của Tâm có n ô (mỗi ô chứa một giá trị nguyên dương không vượt quá 10⁹). Tâm muốn tìm ra dãy con có tổng giá trị lớn nhất từ dãy ban đầu của Tâm. Tâm muốn chọn một ô bất kỳ trong dãy và tính tổng giá trị của dãy con đó, sau đó Tâm sẽ chọn các ô liền kề để tạo thành dãy con mới sao cho tổng giá trị của dãy con đã chọn là lớn nhất.

Yêu cầu: Hãy giúp Tâm tìm ra dãy con có tổng giá trị lớn nhất trong dãy ban đầu của Tâm.

• Số ô trong dãy ban đầu là n.
• Số ô trong dãy con được tính dựa trên tổng giá trị của các ô liền kề.

Yêu cầu: Hãy tính tổng Tâm muốn tìm ra dãy con có tổng giá trị lớn nhất trong dãy ban đầu.

Đầu vào:

• Dòng chứa số n (1 ≤ n ≤ 5000).
• Dòng thứ hai chứa n số a₁, a₂, ..., aₙ (0 ≤ aᵢ ≤ 5000).
• Lưu ý: Có 1 dòng tiêu đề mô tả dãy ban đầu với x, y cho quan hệ cha-con. Nếu 1 ô trên cùng là gốc thì ô đó không có quan hệ cha-con.

Các số trên mỗi dòng được cách nhau bởi dấu cách.

Kết quả: Ghi ra kết quả là tổng giá trị của dãy con có tổng giá trị lớn nhất.

Giải pháp:

• Bộ test được chia làm 3 subtasks:
• Subtask 1 (10% số điểm): n ≤ 30
• Subtask 2 (50% số điểm): n ≤ 300
• Subtask 3 (40% số điểm): Không có ràng buộc số lượng.

Example

Input:
5
5 1 3 0 1
1 2
1 3
3 4
3 5

Output:
4