Chia nhóm

Trong buổi giao lưu giữa các thí sinh của kì thi Tin học trẻ, có học sinh xếp thành một hàng, học
sinh đứng thứ \(i(1 \leq i \leq n)\) đến từ tỉnh có mã là số nguyên \(c_i(1 \leq c_i \leq 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 < k_1 < k_2 ... < k_{g-1} < 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 \(g\) thành nhóm để 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 để tổng độ phong phú của nhóm là lớn nhất.

Input

• Dòng đầu tiên chứa các số nguyên \(n, g\);

• Dòng thứ hai chứa n số nguyên dương \(c_1, c_2, ..., c_n\).

Output

• Ghi ra một dòng chứa một số là tổng độ phong phú của \(g\) nhóm là lớn nhất tìm được.

Example

5 2
1 2 1 3 3

4

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 1000; g = 2\)

• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000; g = 3\)

• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 1000; g \leq 30\)

• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 10^5; g \leq 30\)