Trong lớp học của thầy Kiên, Bờm là một học sinh vô cùng xuất sắc. Hôm nay, Bờm lại tiếp tục đứng nhất trong một Contest giữa các trường, vì thế thầy Kiên quyết định sẽ tặng Bờm một ít kẹo xem như phần thưởng.
Thầy Kiên có viên kẹo được đánh số lần lượt từ đến . Viên kẹo thứ có độ ngon . Hôm nay, thầy quyết định tặng Bờm viên kẹo liên tiếp trong viên kẹo. Mặc khác, vì Bờm rất xuất sắc nên thầy Kiên muốn tổng độ ngon của những viên kẹo Bờm nhận được là lớn
nhất. Bạn hãy giúp thầy Kiên tính toán tổng độ ngon của những viên kẹo mà Bờm sẽ nhận được nhé!
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương và là số lượng kẹo của thầy Kiên;
Dòng thứ trong dòng tiếp theo chứa duy nhất một số nguyên là độ ngon của viên kẹo thứ .
Dữ liệu ra:
Đưa ra kết quả bài toán trên một dòng.
Ví dụ:
Dữ liệu vào:
5 2
4
3
2
6
1
Dữ liệu ra:
8
Giải thích:
Thầy Kiên cần chọn viên kẹo liên tiếp sao cho tổng độ ngon là lớn nhất, vì thế thầy sẽ chọn viên kẹo thứ và viên kẹo thứ .
Giới hạn:
số test ứng với số điểm có ;
số test còn lại ứng với số điểm không có giới hạn gì thêm.
