Problem Description

Pitaro is playing a board game. There are $M$ consecutive squares numbered from $1$ to $M$ from left to right, and $N$ pieces are placed on these squares. Each piece is numbered from $1$ to $N$, and piece $i$ is on square $x_i$.

A positive integer $K$ is given. Pitaro can perform operations $1$ to $K$ once each, in any order, and some operations may be skipped.

Operation $i$ $(1 \leq i \leq K)$

• Select a piece that has never been moved and move it $i$ squares.
• That is, if the selected piece is on square $a$, move it to square $a-i$ or square $a+i$.
• If the destination square is outside the $M$ squares, the piece cannot be moved.
• It is acceptable if the destination square already has a piece on it.

Pitaro is trying to gather as many pieces as possible on one square. Write a program to find the maximum number of pieces that can be placed on one square when optimal operations are performed.

Input Format

The input is given from the standard input in the following format:

$M$ $N$ $K$ $x_1$ $x_2$ $\cdots$ $x_N$

Output Format

Output the maximum number of pieces that can be placed on one square to the standard output in one line.

Sample Input and Output

Sample Input #1

5 3 1
1 2 3

Sample Output #1

2

Sample Input #2

4 3 3
1 4 4

Sample Output #2

3

Sample Input #3

4 2 2
4 1

Sample Output #3

2

Sample Input #4

3 2 1
1 3

Sample Output #4

1

Sample Input #5

5 3 2
2 5 4

Sample Output #5

3

Sample Input #6

10 5 4
1 4 1 8 7

Sample Output #6

4

Notes/Hints

Constraints

• All input values are integers.
• $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)$

Subtasks

1. ($12$ points) $x_i = i$ $(1 \leq i \leq N)$
2. ($13$ points) $x_i$ $(1 \leq i \leq N)$ can only take $2$ distinct values.
3. ($20$ points) $K \leq 2$
4. ($55$ points) No additional constraints.

Sample Explanation 1

Perform operation $1$ to move piece $1$ from square $1$ to square $2$. Since operation $1$ can only be performed once, this is optimal.

Sample Explanation 2

Multiple pieces can be on the same square. Perform operation $3$ to move piece $1$ from square $1$ to square $4$.

Sample Explanation 3

Since operation $3$ cannot be performed, it is impossible to gather $2$ pieces on squares $1$ and $4$. However, by performing operation $1$ and operation $2$ once each, it is possible to gather $2$ pieces on square $2$.

Sample Explanation 4

Operation $2$ cannot be performed, and operation $1$ can only be performed once.

见题面 Input 部分

见题面 Output 部分