Đóng gói lô dữ liệu

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

Có dãy n khối dữ liệu. Bạn phải chia dãy thành các đoạn liên tiếp, mỗi đoạn dài không quá K. Sau khi đóng gói, mọi phần tử trong đoạn được quy đổi thành giá trị lớn nhất của đoạn; điểm đoạn bằng giá trị lớn nhất nhân độ dài đoạn.

Yêu cầu

Tối đa hóa tổng điểm của toàn bộ dãy sau khi chia.

Input

Dòng 1 n K; dòng 2 dãy a.

Output

In tổng điểm lớn nhất.

Ràng buộc

• 1 <= n <= 5000
• 1 <= K <= 100
• 0 <= a_i <= 10^9

Chấm điểm

Ví dụ 1

Input

7 3
1 15 7 9 2 5 10

Output

84

Giải thích. Ví dụ nhỏ giúp kiểm tra cách chia prefix thành các đoạn liên tiếp và đánh giá điểm của đoạn cuối.

Ví dụ 2

Input

5 1
2 4 1 8 3

Output

18

Giải thích. Khi K = 1, mỗi phần tử bắt buộc tạo thành một đoạn riêng.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.