AT_abc480_f [ABC480F] Cake Cutting

$ N $ 個のケーキがあり、 $ i $ 個目のケーキの大きさは $ A_i $ です。これらのケーキを $ M $ 人に配ろうとしています。 ケーキの大きさの総和 $ A_1+\dots+A_N $ を $ S $ とします。 ここで、 $ S $ は $ M $ の倍数であることが保証されます。 あなたは、以下の操作を好きな順序で好きな回数( $ 0 $ 回でもよい)行うことができます。 - ケーキを $ 1 $ つ選び、それを自由に $ 2 $ つに切り分ける(大きさが整数である必要はない)。 操作後、ケーキを $ M $ 人に配ります。どの人がもらうケーキの大きさの合計も $ \frac{S}{M} $ となるようにするための、操作回数の最小値を求めてください。 より厳密な問題文は以下の通りです。 - 列 $ A=(A_1,\dots,A_N) $ と正整数 $ M $ が与えられる。 $ S=\sum_i A_i $ と定める。 - 以下の操作を好きな回数行う。 - $ 1\leq i \leq |A| $ を満たす整数 $ i $ と $ 0 < x < A_i $ を満たす実数 $ x $ を自由に選ぶ。 $ A $ の末尾に $ x,A_i-x $ を追加し、 $ i $ 番目の要素を削除した長さ $ |A|+1 $ の列で $ A $ を置き換える。 - 以下の条件を全て満たす $ \mathcal{P} $ が存在するための最小の操作回数を求めよ。 - $ \mathcal{P} $ は $ \{1,2,\dots,|A|\} $ の分割である。即ち、以下の $ 3 $ 条件を満たす集合である。 - $ \mathcal{P} $ の各要素は $ \{1,2,\dots,|A|\} $ の部分集合である。 - $ X,Y \in \mathcal{P} $ かつ $ X\neq Y $ ならば、 $ X \cap Y = \emptyset $ である。 - $ \bigcup_{X \in \mathcal{P}}X=\{1,2,\dots,|A|\} $ が成り立つ。 - すべての $ X\in \mathcal{P} $ について、 $ \sum_{i\in X}A_i=\frac{S}{M} $ が成り立つ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 次のように $ 2 $ 回の操作を行うのが最小です。 - 大きさ $ 23 $ のケーキを大きさ $ 10,13 $ に切り分ける。ケーキの大きさはそれぞれ $ (7,10,13) $ になる。 - 大きさ $ 13 $ のケーキを大きさ $ 10,3 $ に切り分ける。ケーキの大きさはそれぞれ $ (7,10,10,3) $ になる。 - 「大きさ $ 7 $ のケーキと大きさ $ 3 $ のケーキ」「大きさ $ 10 $ のケーキ」「大きさ $ 10 $ のケーキ」をそれぞれの人に与える。 ### Sample Explanation 2 次のように $ 1 $ 回の操作を行うのが最小です。 - 大きさ $ 1234 $ のケーキを大きさ $ 685,549 $ に切り分ける。ケーキの大きさはそれぞれ $ (123,12,1,685,549) $ になる。 - 「大きさ $ 123,12,1,549 $ の $ 4 $ 個のケーキ」「大きさ $ 685 $ のケーキ」をそれぞれの人に与える。 ### Constraints - $ 1 \leq N \leq 20 $ - $ 1 \leq M \leq 100 $ - $ 1 \leq A_i \leq 10^9 $ - $ A_1+\dots+A_N $ は $ M $ の倍数 - 与えられる数値は全て整数