AT_abc480_f [ABC480F] Cake Cutting

There are $ N $ cakes, and the size of the $ i $ -th cake is $ A_i $ . You are going to distribute these cakes to $ M $ people. Let $ S $ be the total size of the cakes, $ A_1+\dots+A_N $ . Here, it is guaranteed that $ S $ is a multiple of $ M $ . You can perform the following operation any number of times (possibly zero) in any order. - Choose one cake and cut it into $ 2 $ pieces in any way you like (the sizes need not be integers). After the operations, you distribute the cakes to the $ M $ people. Find the minimum number of operations required so that the total size of the cakes each person receives is $ \frac{S}{M} $ . A more formal statement is as follows. - You are given a sequence $ A=(A_1,\dots,A_N) $ and a positive integer $ M $ . Let $ S=\sum_i A_i $ . - You can perform the following operation any number of times. - Choose an integer $ i $ with $ 1\leq i \leq |A| $ and a real number $ x $ with $ 0 < x < A_i $ . Replace $ A $ with the sequence of length $ |A|+1 $ obtained by appending $ x,A_i-x $ to the end of $ A $ and removing the $ i $ -th element. - Find the minimum number of operations required for there to exist a $ \mathcal{P} $ satisfying all of the following conditions. - $ \mathcal{P} $ is a partition of $ \{1,2,\dots,|A|\} $ ; that is, it is a set satisfying the following $ 3 $ conditions. - Each element of $ \mathcal{P} $ is a subset of $ \{1,2,\dots,|A|\} $ . - If $ X,Y \in \mathcal{P} $ and $ X\neq Y $ , then $ X \cap Y = \emptyset $ . - $ \bigcup_{X \in \mathcal{P}}X=\{1,2,\dots,|A|\} $ holds. - $ \sum_{i\in X}A_i=\frac{S}{M} $ holds for every $ X\in \mathcal{P} $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Print the answer.

### Sample Explanation 1 The minimum is achieved by performing $ 2 $ operations as follows. - Cut the cake of size $ 23 $ into pieces of sizes $ 10 $ and $ 13 $ . The cake sizes become $ (7,10,13) $ . - Cut the cake of size $ 13 $ into pieces of sizes $ 10 $ and $ 3 $ . The cake sizes become $ (7,10,10,3) $ . - Give the cakes of sizes $ 7 $ and $ 3 $ to one person, a cake of size $ 10 $ to another person, and the remaining cake of size $ 10 $ to the last person. ### Sample Explanation 2 The minimum is achieved by performing $ 1 $ operation as follows. - Cut the cake of size $ 1234 $ into pieces of sizes $ 685 $ and $ 549 $ . The cake sizes become $ (123,12,1,685,549) $ . - Give the $ 4 $ cakes of sizes $ 123,12,1,549 $ to one person and the cake of size $ 685 $ to the other. ### Constraints - $ 1 \leq N \leq 20 $ - $ 1 \leq M \leq 100 $ - $ 1 \leq A_i \leq 10^9 $ - $ A_1+\dots+A_N $ is a multiple of $ M $ . - All input values are integers.