题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,...,a_n$ 和一个参数 $k$。

请问如何将该序列分成连续的 $k$ 段，使得每一段众数出现的次数之和最大？

输入格式

输入共两行： 第一行，两个正整数 $n,k$ 第二行，$n$ 个正整数 $a_1,...,a_n$

输出格式

输出共一行，一个整数，表示答案

6 2
6 2 6 9 1 1

4

样例解释 1

可以分成[6,2,6]和[9,1,1]两段 或是分成[6,2,6,9]和[1,1]两段

数据范围

• 对于 $30\%$ 的数据，$1 \leq n \leq 10,1 \leq k \leq n$
• 对于 $60\%$ 的数据，$1 \leq n \leq 10^3$
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5,1 \leq k \leq 100$,$1 \leq a_i\leq 10^9$