配点: 100 点
問題
Pitaro 正在玩棋盘游戏。从左边开始 编号为 1 ~ M 被给予了一个号码 M 在旁边的一个连续的正方形中 N 件已放置。对于碎片 这些作品的编号为 1 ~ N 。 i 是质量 给出了 x_i 在。
正整数 K 。 Pitaro 的操作如下图所示。 1 ~ K 该值应乘以 1 您可以一次执行一次此操作。您可以按照任意顺序执行操作,并且某些操作可能无法执行。
操作 i (1 \leq i \leq K)
- 从未移动过的碎片 1 选择一项,i 移动方块。
- 换句话说,所选的片段是 a ,这件作品被聚集在一起。 a-i 或质量 将其移至 a+i 。
- 目的地是 如果棋子超出 M 方格,则无法移动。
- 棋子是否已放置在目的地并不重要。
Pitaro 正在尝试在某个方块中收集更多碎片。编写一个程序,在执行最佳操作时找到放置在某个方格上的最大棋子数量。
制約
- 所有输入均为整数。
- 1 \leq M \leq 2\,000
- 1 \leq N \leq 2\,000.
- 1 \leq K \leq 2\,000.
- 1 \leq x_i \leq M (1 \leq i \leq N).
小課題
- (12 点) x_i = i (1 \leq i \leq N).
- (13 点) x_i (1 \leq i \leq N) 的可能值为 2 仅类型。
- (20 点) K \leq 2.
- (55 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
M N K x_1 x_2 \cdots x_N
出力
将放置在某个方格上的最大棋子数量输出到标准输出。 1 逐行输出。
入力例 1
5 3 1 1 2 3
出力例 1
2
操作 1 和 1 中的片段 1 只需将其移至 2 即可。操作 这是最佳选择,因为它只能执行 1 是 您也可以写 1 次。
入力例 2
4 3 3 1 4 4
出力例 2
3
1 有时,一个方格中会放置多个棋子。操作 只需将其移至 3 和 1 中的片段 1 只需将其移至 4 即可。
入力例 3
4 2 2 4 1
出力例 3
2
操作 3 无法执行,因此质量 1 和质量 4 有 直到 2 件。然而,操作 1 和操作 通过执行 2 该值应乘以 1 次,您可以 2 至 该值是 2 件。
入力例 4
3 2 1 1 3
出力例 4
1
操作 2 无法执行并且操作 您只能执行 1 是 您也可以写 1 次。
入力例 5
5 3 2 2 5 4
出力例 5
3
入力例 6
10 5 4 1 4 1 8 7
出力例 6
4