B. Кондитерская
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На днях Сластена решила опробовать себя в производстве сладостей и открыть собственную кондитерскую! Для этого она купила нужные ингредиенты и чудо-печку, которая способна выпекать несколько различных видов пирожных; и запустила производство.

Сразу же возникли проблемы: расходы на содержание кондитерской быстро начали превышать выручку от проданных пирожных. Сластена смекнула, что надо менять ценовую политику, и решила исследовать рынок сладостей. Оказалось, что чем больше в коробке различных видов пирожных (назовем это число ценностью коробки с пирожными), тем больше денег за нее готовы предложить покупатели.

Нужно срочно менять технологию производства! Но вот незадача: выбор конкретных видов пирожного печка делает сама, и Сластена никак не может повлиять на принцип ее действия. Однако, она знает, в каком порядке выйдут n пирожных из печки сегодня. Сластена сегодня должна упаковать ровно k коробок с пирожными, причем в каждую коробку она должна положить несколько (не меньше одного) пирожных, которые печка испекла подряд, так как коробка должна сразу же отправиться на прилавок.

Сластена хочет максимизировать суммарную ценность всех коробок с пирожными. Помогите ей определить эту максимальную ценность.

Входные данные

В первой строке даны числа n и k (1 ≤ n ≤ 35000, 1 ≤ k ≤ min(n, 50)) — число пирожных и количество коробок соответственно.

Во второй строке дано n чисел a1, a2, ..., an (1 ≤ ai ≤ n) — виды пирожных в порядке, в котором печка их выпекает.

Выходные данные

Выведите единственное число — максимально возможную суммарную ценность коробок с пирожными.

Примеры
Входные данные
4 1
1 2 2 1
Выходные данные
2
Входные данные
7 2
1 3 3 1 4 4 4
Выходные данные
5
Входные данные
8 3
7 7 8 7 7 8 1 7
Выходные данные
6
Примечание

В первом примере в распоряжении Сластены есть одна коробка. Оптимально расфасовать туда все доступные пирожные и получить два различных вида пирожных с суммарной ценностью 2.

Во втором примере разумно положить первые два пирожных в первую коробку, а оставшиеся — во вторую. Таким образом мы получим два и три различных вида пирожных, которые обеспечивают суммарную стоимость 5.