← 返回题目列表

Codeforces · 833/B

B. 面包店

中文机器翻译题面 查看原题

不久前,Sweetmaid Slastyona 决定开设自己的面包店!她买了所需的原料和一个可以烤多种蛋糕的神奇烤箱,开了一家面包店。

很快,支出开始超过收入,因此 Slastyona 决定研究糖果市场。她了解到,将蛋糕包装在盒子里是有利可图的,而且盒子里的蛋糕类型越多(我们将这个数字表示为盒子的价值),它的价格就越高。

她需要改变生产技术!问题是烤箱会自行选择蛋糕类型,Slastyona 无法影响它。不过,她知道今天烤箱要烤的 n 个蛋糕的种类和顺序。今天,Slastyona 必须装满 k 个蛋糕盒子,并且她必须在每个盒子里放入几个(至少一个)烤箱一个接一个地制作的蛋糕(换句话说,她必须在一个盒子里放入连续的一段蛋糕)。

Slastyona 希望最大化所有装有蛋糕的盒子的总价值。帮助她确定这个最大可能的总价值。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 35000, 1 ≤ k ≤ min(n, 50)) – 分别是蛋糕的数量和盒子的数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n) – 蛋糕的类型(按烤箱烘烤的顺序排列)。

输出

打印唯一的整数——所有装有蛋糕的盒子的最大总价值。

示例

输入 #1

4 1
1 2 2 1

输出 #1

2

输入 #2

7 2
1 3 3 1 4 4 4

输出 #2

5

输入 #3

8 3
7 7 8 7 7 8 1 7

输出 #3

6

注意

在第一个示例中,Slastyona 只有一个盒子。她必须把所有的蛋糕都放进去,这样盒子里就有两种蛋糕,所以值就等于2。

在第二个示例中,将前两个蛋糕放入第一个盒子中,将其余所有蛋糕放入第二个盒子中是有利可图的。第一个框中有两种不同的类型,第二个框中有三种不同的类型,因此总值为 5。