Tèo là người chiến thắng trong chương trình bốc thăm trúng thưởng của một cửa hàng. Người chủ giới thiệu n phần thưởng mà Tèo có thể chọn. Các phần thưởng được xếp thành một dãy, phần thưởng ở vị trí i có giá trị a_i (VNĐ); i = 1, 2, …, n. Lần lượt đi từ trái sang phải theo chiều tăng dần của i, Tèo có quyền bỏ qua một số phần thưởng và chọn những phần thưởng tùy ý, nhưng không được quay lại những phần thưởng đã bỏ qua cũng như không được thay đổi quyết định đã đưa ra trước đó. Ngoài ra, phần thưởng chọn tiếp theo phải có giá trị lớn hơn giá trị phần thưởng vừa chọn trước đó.

Nếu tổng giải thưởng được chọn là lớn nhất trong số các cách chọn hợp lệ thì Tèo sẽ nhận được mọi thứ đã chọn, nếu không sẽ phải ra về trắng tay.

Nhưng với trí nhớ tốt, trạng thái tâm lý vững vàng và khả năng tính toán tốt Tèo đã nhận được phần thưởng của cửa hàng.

Yêu cầu: Em hãy lập trình xác định tổng giá trị phần thưởng mà Tèo đã nhận được.

Dữ liệu: Vào từ tệp văn bản PRIZES.INP có cấu trúc như sau:

+ Dòng thứ nhất ghi số nguyên dương n là số phần thưởng (n ≤ 10³).

+ Dòng thứ hai gồm n số nguyên dương a₁, a₂, …, a_n (a₁, a₂, …, a_n ≤ 10⁹) là giá trị của các phần thưởng.

Hai số ghi trên một dòng cách nhau bởi một dấu cách.

Kết quả: Ghi ra tệp văn bản PRIZES.OUT một số nguyên là tổng giá trị phần thưởng mà Tèo đã nhận được.

Ví dụ:

Chấm điểm:

Subtask 1 (50%) : n ≤ 100; a_i ≤ 1000.

Subtask 2 (50%) : Không có ràng buộc gì thêm.