Tý có \(N\) đống đá xếp thành một vòng tròn. Đống thứ i có trọng lượng \(a_i\). Mỗi bước chọn hai đống kề nhau gộp lại (\(chi phí = tổng trọng lượng\)). Tìm tổng chi phí nhỏ nhất gộp tất cả thành một đống.

#

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le N \le 500, 2 \le K \le N\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^4\)).

Định dạng đầu ra

• In ra chi phí tối thiểu để gộp \(N\) đống thành 1 đống (mỗi lần gộp đúng \(K\) đống liên tiếp), hoặc -1 nếu không thể.

Ví dụ

Input:

5 3
1 2 3 4 5

Output:

21

Giải thích: Gộp [1,2,3]->6 (chi phí 6), dãy thành [6, 4, 5]. Gộp [6,4,5]->15 (chi phí 15). Tổng = 21.

Ràng buộc & Subtasks