AT_otemae2019_b 駒 (Pieces)

皮太郎在玩棋盘游戏。从左到右编号为 $1$ ～ $M$ 的 $M$ 个旁边连续的棋子上放置着 $N$ 个棋子。棋子上有 $1$ ～ $N$ 的号码， $i$ 号棋子为 $x_i$ 。 给定正整数 $K$ 。皮太郎可以将以下所示的操作 $1$ ～ $K$ 每次进行 $1$ 次。可以按照任何顺序进行操作，也可以有不进行的操作。 #### 操作 $i$ $(1\ \leq\ i\ \leq\ K)$ - 选择一次也没有被移动过的棋子$1$，移动$i$。 - 选择的棋子在棋子 $a$ 时，将棋子移动到棋子 $a-i$ 或棋子 $a+i$。 - 移动目的地超出 $M$ 格时不能移动棋子。 - 移动目的地已经放置棋子也没关系。 皮太郎想在某个方格上收集更多的棋子。制作出在进行最合适操作时，求放置在某个方格上的棋子个数的最大值的程序。

输入以以下形式从标准输入被给予。 > $ M $ $ N $ $ K $ $ x_1 $ $ x_2 $ $ \cdots $ $ x_N $

输出共 $1$ 行，将放置在某个格子中的棋子个数的最大值。

### 约束条件 - 输入的所有数据均为整数。 - $ 1 \leq M \leq 2000 $ - $ 1 \leq N \leq 2000 $ - $ 1 \leq K \leq 2000 $ - $ 1 \leq x_i \leq M $ 对于 （ $1 \leq i \leq N $ ）。 ### 子任务 1. $12$ 分 $ x_i = i $ 对于 $1 \leq i \leq N$。 2. $13$ 分 $ x_i $ 仅能取 $2$ 种值。 3. $20$ 分 $ K \leq 2 $。 4. $55$ 分 无额外约束条件。 执行操作 $1$，将位于格子 $1$ 的棋子 $1$ 移动到格子 $2$。由于操作 $1$ 只能执行一次，因此这是最优解。 一个格子中可以放置多个棋子。执行操作 $3$，将位于格子 $1$ 的棋子 $1$ 移动到格子 $4$。 由于无法执行操作 $3$，因此无法在格子 $1$ 和格子 $4$ 中收集到 $2$ 个棋子。然而，通过分别执行操作 $1$ 和操作 $2$ 各一次，可以将 $2$ 个棋子收集到格子 $2$。 无法执行操作 $2$，而且操作 $1$ 只能执行一次。