不久前,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。