The Bakery

얼마 전 Slastyona the Sweetmaid는 자신의 빵집을 열기로 했다! 그녀는 필요한 재료와 여러 종류의 케이크를 구울 수 있는 신기한 오븐을 산 뒤 빵집을 열었다.

얼마 지나지 않아 지출이 수입을 넘어서기 시작했고, Slastyona는 과자 시장을 조사하기로 했다. 그녀는 케이크를 상자에 포장하는 것이 이익이며, 상자에 서로 다른 종류의 케이크가 많이 들어 있을수록(이 종류의 수를 상자의 가치라고 하자) 가격이 더 높다는 사실을 알게 되었다.

그녀는 생산 방식을 바꿔야 한다! 문제는 오븐이 케이크의 종류를 스스로 선택하므로 Slastyona가 이에 영향을 줄 수 없다는 것이다. 하지만 그녀는 오븐이 오늘 구울 n개 케이크의 종류와 순서를 알고 있다. Slastyona는 오늘 케이크를 정확히 k개의 상자에 포장해야 하며, 각 상자에는 오븐이 연달아 생산한 여러 개의(적어도 하나의) 케이크를 넣어야 한다(다시 말해, 각 상자에는 케이크의 연속 구간을 넣어야 한다).

Slastyona는 케이크가 든 모든 상자의 가치 합을 최대화하려 한다. 가능한 가치 합의 최댓값을 구하도록 도와주자.

첫 번째 줄에는 두 정수 n와 k가 주어진다(1 ≤ n ≤ 35000, 1 ≤ k ≤ min(n, 50)). 각각 케이크의 수와 상자의 수를 나타낸다.

두 번째 줄에는 오븐이 케이크를 굽는 순서대로 케이크의 종류를 나타내는 n개의 정수 a1, a2, ..., 그리고 (1 ≤ ai ≤ n)가 주어진다.

케이크가 든 모든 상자의 가치 합의 최댓값을 나타내는 유일한 정수를 출력한다.

첫 번째 예제에서 Slastyona에게는 상자가 하나뿐이다. 모든 케이크를 그 상자에 넣어야 하므로 상자에는 두 종류의 케이크가 들어가고, 그 가치는 2가 된다.

두 번째 예제에서는 처음 두 케이크를 첫 번째 상자에 넣고 나머지를 모두 두 번째 상자에 넣는 것이 이익이다. 그러면 첫 번째 상자에는 서로 다른 두 종류가 있고 두 번째 상자에는 세 종류가 있으므로, 가치 합은 5가 된다.