Hôm nay là ngày sinh nhật của m bạn trong lớp. Để chúc mừng các bạn, cả lớp đã mua n gói kẹo mỗi gói chứa một loại kẹo là một số nguyên dương nằm trong khoảng từ 1 đến n. Lớp trưởng xếp các gói kẹo này thành một dãy, đánh số lần lượt từ 1 đến n. Sau đó lớp trưởng sẽ chia dãy này thành m đoạn liên tiếp, mỗi bạn được mừng sinh nhật sẽ chọn một đoạn trong số m đoạn nói trên. Mỗi bạn đều thích dãy các gói kẹo của mình càng nhiều loại càng tốt. Do vậy giá trị của một đoạn được tính bằng số loại kẹo khác nhau có trong đoạn.
Yêu cầu: Hãy tìm cách chia dãy các gói kẹo thành m đoạn khác rỗng sao cho tổng giá trị các đoạn được chia là lớn nhất.

Input:

• Dòng đầu chứa hai số nguyên dương n, m (1 ≤ n ≤ 50000, 1 ≤ m ≤ min(n, 50))
• Dòng thứ hai chứa n số nguyên a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ n) lần lượt là loại kẹo của gói kẹo 1, 2, ..., n.

Output:

• Một số nguyên duy nhất là giá trị lớn nhất của tổng giá trị các đoạn.

Example: