AT_otemae2019_b 駒 (Pieces)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_b ピ太郎はボードゲームで遊んでいる．左から $ 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\ 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 $ 点) 追加の制約はない． ### Sample Explanation 1 操作 $ 1 $ を行い，マス $ 1 $ にある駒 $ 1 $ をマス $ 2 $ に移動させればよい．操作 $ 1 $ は $ 1 $ 回しか行えないため，これが最適となる． ### Sample Explanation 2 $ 1 $ つのマスに複数の駒が置かれていることもある．操作 $ 3 $ を行い，マス $ 1 $ にある駒 $ 1 $ をマス $ 4 $ に移動させればよい． ### Sample Explanation 3 操作 $ 3 $ は行えないため，マス $ 1 $ およびマス $ 4 $ には $ 2 $ 個の駒を集めることができない．しかし，操作 $ 1 $ と操作 $ 2 $ を $ 1 $ 回ずつ行うことで，マス $ 2 $ に $ 2 $ 個の駒を集めることができる． ### Sample Explanation 4 操作 $ 2 $ は行えないし，操作 $ 1 $ は $ 1 $ 回しか行えない．