| Codeforces Round 426 (Div. 1) |
|---|
| Закончено |
На днях Сластена решила опробовать себя в производстве сладостей и открыть собственную кондитерскую! Для этого она купила нужные ингредиенты и чудо-печку, которая способна выпекать несколько различных видов пирожных; и запустила производство.
Сразу же возникли проблемы: расходы на содержание кондитерской быстро начали превышать выручку от проданных пирожных. Сластена смекнула, что надо менять ценовую политику, и решила исследовать рынок сладостей. Оказалось, что чем больше в коробке различных видов пирожных (назовем это число ценностью коробки с пирожными), тем больше денег за нее готовы предложить покупатели.
Нужно срочно менять технологию производства! Но вот незадача: выбор конкретных видов пирожного печка делает сама, и Сластена никак не может повлиять на принцип ее действия. Однако, она знает, в каком порядке выйдут 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.
