题目描述

不久前，Slastyona the Sweetmaid 决定开设自己的面包店！她买齐了所需的原料，还有一台可以烘焙多种蛋糕的奇妙烤箱，并开张了面包店。

很快，开支开始超过收入，于是 Slastyona 决定研究甜点市场。她了解到，将蛋糕装入盒子会更有利可图，而且每个盒子里不同种类蛋糕越多（我们将这个数量称为盒子的价值），价格就越高。

她需要改变生产技术！问题在于，烤箱会自行决定蛋糕的种类，Slastyona 无法干预。然而，她知道今天烤箱将要依次烘烤出 $n$ 个蛋糕的类型和顺序。今天，Slastyona 必须准确地用 $k$ 个盒子来打包这些蛋糕，并且每个盒子内必须放入若干（至少一个）连续烘焙出来的蛋糕（换句话说，每个盒子包含一段蛋糕的连续区间）。

Slastyona 希望最大化所有盒子的总价值。请你帮她求出所有盒子的最大可能总价值。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 35000$，$1 \leq k \leq \min(n, 50)$）——蛋糕的数量以及盒子的数量。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, ..., a_{n}$（$1 \leq a_{i} \leq n$）——按照烤箱生产顺序排列的蛋糕类型。

输出格式

输出唯一一个整数，表示所有盒子中的蛋糕最大可能的总价值。

输入输出样例 #1

输入 #1

4 1
1 2 2 1

输出 #1

2

输入输出样例 #2

输入 #2

7 2
1 3 3 1 4 4 4

输出 #2

5

输入输出样例 #3

输入 #3

8 3
7 7 8 7 7 8 1 7

输出 #3

6

说明/提示

在第一个样例中，Slastyona 只有一个盒子。她必须把所有蛋糕都放进这个盒子里，因此这个盒子有两种类型，价值为 $2$。

在第二个样例中，最优策略是将前两个蛋糕放入第一个盒子，其余的都放进第二个盒子。则第一个盒子有两种类型，第二个盒子有三种类型，因此总价值为 $5$。

由 ChatGPT 5 翻译