24442번 - 수열 쪼개기

문제

길이 $N$인 수열 $A_1, A_2, \dots , A_N $이 있다.

이 수열을 순서를 바꾸지 않고 $K$개의 수열로 쪼갤 수 있다.

예를 들어 수열 [1, 3, 5, 7, 9]를 [1], [3, 5], [7, 9] 와 같이 3개의 수열로 쪼갤 수 있다. 하지만 [1], [3, 7], [5, 9] 와 같이 쪼갤 수는 없다.

이 때 모든 수열은 하나 이상의 수를 포함해야 하고 모든 수는 정확히 하나의 수열에 포함되어야 한다.

수열에 포함된 서로 다른 수의 개수를 수열의 가치로 정의하자.

쪼개진 수열들의 가치의 합의 최댓값을 구하시오.

입력

첫 번째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1\leq K \leq N \leq 2\times 10^5)$

두 번째 줄에 $N$개의 정수 $A_1,A_2, \dots , A_N$이 공백으로 구분되어 주어진다. $(1\leq A_1, A_2, \dots , A_N \leq N)$

출력

첫 번째 줄에 쪼개진 수열들의 가치의 합의 최댓값을 출력한다.

제한

힌트