Trong buổi giao lưu giữa các thí sinh của kì thi Tin học trẻ, có \(n\) học sinh xếp thành một hàng, học sinh đứng thứ \(i (1 \le i \le n)\) đến từ tỉnh có mã là số nguyên \(c_i (1 \le c_i \le 63)\). Ban tổ chức muốn tách hàng để nhận được \(g\) nhóm học sinh tham gia một trò chơi. Cụ thể, Ban tổ chức cần chọn ra \(g-1\) điểm cắt \(1 \lt k_1 \lt k_2 \lt .. \lt k_{g-1} \lt n\), khi đó các bạn từ đầu hàng đến bạn đứng thứ \(k_1\) sẽ xếp vào nhóm thứ nhất, các bạn đứng thứ \(k_1 + 1\) đến \(k_2\) sẽ xếp vào nhóm thứ hai... bạn đứng thứ \(k_{g-1}+1\) đến \(n\) xếp vào nhóm thứ \(g\). Độ phong phú của một nhóm được tính bằng số lượng tỉnh khác nhau của học sinh trong nhóm. Để các thí sinh có nhiều cơ hội giao lưu với nhau, Ban tổ chức muốn tìm cách tách hàng thành \(g\) nhóm để có tổng độ phong phú của g nhóm là lớn nhất.

Yêu cầu: Cho dãy số nguyên dương \(c_1, c_2, ... c_n\) và số nguyên dương \(g\), hãy tìm cách tách hàng thành \(g\) nhóm để có tổng độ phong phú của \(g\) nhóm là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên gồm các số nguyên dương n, g;
• Dòng thứ hai chứa \(n\) số nguyên dương \(c_1, c_2, ... c_n\).

Kết quả: Một số là tổng độ phong phú lớn nhất tìm được.

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài có \(n \le 1000\) và \(g=2\);
• Có 25% số test khác ứng với 25% số điểm của bài có \(n \le 1000; g = 3\);
• Có 25% số test khác ứng với 25% số điểm của bài có \(n \le 1000; g \le 30\);
• Có 25% số test khác ứng với 25% số điểm của bài có \(n \le 10^5; g \le 30\);

Dữ liệu vào

5 2
1 2 1 3 3

Kết quả

4