Ban tổ chức một lễ hội âm nhạc lớn kéo dài ngày. Đối với mỗi ngày, họ đã ước tính một "chỉ số sôi động", có thể là một số dương (nếu ngày đó có các nghệ sĩ nổi tiếng, thời tiết đẹp) hoặc số âm (nếu có sự cố kỹ thuật, thời tiết xấu).
Để lấp đầy lịch trình, ban tổ chức quyết định sẽ lên kế hoạch cho đúng sự kiện đặc biệt khác nhau. Mỗi sự kiện sẽ diễn ra trong một khoảng ngày liên tiếp. Có hai yêu cầu bắt buộc:
Tất cả sự kiện được chọn phải là khác nhau (tức là không có hai sự kiện nào bắt đầu và kết thúc vào cùng một ngày).
Để đảm bảo lễ hội luôn có sự kiện hoạt động, mỗi ngày trong ngày đều phải thuộc về ít nhất một sự kiện.
"Điểm danh tiếng" của một sự kiện được tính bằng tổng các chỉ số sôi động của những ngày mà nó diễn ra. Tổng danh tiếng của lễ hội là tổng của "điểm danh tiếng" từ tất cả sự kiện đã được chọn.
Bạn hãy giúp ban tổ chức lựa chọn chính xác sự kiện thỏa mãn các điều kiện trên sao cho tổng danh tiếng của lễ hội là lớn nhất có thể.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và (, ) — số ngày diễn ra lễ hội và số lượng sự kiện cần tổ chức.
Dòng thứ hai chứa số nguyên () — chỉ số sôi động của từng ngày trong lễ hội.
Kết quả: In ra một số nguyên duy nhất là tổng danh tiếng lớn nhất có thể đạt được.
Ví dụ:
Dữ liệu:
5 4
6 -4 -10 -4 7
Kết quả:
11
Giải thích: Ban tổ chức cần chọn ra 4 sự kiện khác nhau. Một trong những phương án lựa chọn tối ưu là:
Sự kiện 1: Diễn ra vào ngày 1 (đoạn con [6]). Điểm danh tiếng: 6.
Sự kiện 2: Diễn ra vào ngày 5 (đoạn con [7]). Điểm danh tiếng: 7.
Sự kiện 3: Diễn ra từ ngày 1 đến ngày 5 (đoạn con [6, -4, -10, -4, 7]). Điểm danh tiếng: -5.
Sự kiện 4: Diễn ra từ ngày 4 đến ngày 5 (đoạn con [-4, 7]). Điểm danh tiếng: 3.
Tất cả 5 ngày của lễ hội đều được bao phủ bởi ít nhất một sự kiện. Tổng danh tiếng đạt được là: .
