問題

ピ太郎はボードゲームで遊んでいる．左から 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 個のマスからはみ出してしまう場合は駒を動かすことができない．
• 移動先にすでに駒が置かれていても構わない．

ピ太郎は，どこかのマスにより多くの駒を集めようとしている．最適な操作をしたときの，あるマスに置かれた駒の個数の最大値を求めるプログラムを作成せよ．

制約

• 入力はすべて整数である．
• 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)．

小課題

1. (12 点) x_i = i (1 \leq i \leq N)．
2. (13 点) x_i (1 \leq i \leq N) が取り得る値は 2 種類のみである．
3. (20 点) K \leq 2．
4. (55 点) 追加の制約はない．

入力例 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