Grinding Gravel

문제

During the renovation of your garden, you decide that you want a gravel path running from the street to your front door. Being a member of the Boulders And Pebbles Community, you want this path to look perfect. You already have a regular grid to put the gravel in, as well as a large container of gravel containing exactly as much as the total capacity of the grid.

There is one problem: the gravel does not yet fit perfectly into the grid. Each grid cell has the same (fixed) capacity and every piece of gravel has a certain weight. You have a grindstone that can be used to split the stones into multiple pieces, but doing so takes time, so you want to do a minimal number of splits such that the gravel can be exactly distributed over the grid.

As an example, consider the first sample case. There are three grid cells of size $88$, which can be filled as follows. Put the stones of weight $22$ and $66$ in the first cell. Now grind the stone of weight $77$ into two pieces of weight $33$ and $44$. Then the other two grid cells get filled by weights $3,53,\; 5$ and $4,44,\; 4$ respectively.

입력

The input consists of:

• One line with two integers $nn$ and $kk$ ($1\le n\le 1001\; \backslash leq\; n\; \backslash leq\; 100$, $1\le k\le 81\; \backslash leq\; k\; \backslash leq\; 8$), the number of pieces of gravel and the capacity per grid cell.
• One line with $nn$ integers $w_1,\dots ,w_{n}w\_1,\; \backslash dots,\; w\_n$ ($1\le w_i\le {10}^{6}1\; \backslash leq\; w\_i\; \backslash leq\; 10^6$ for all $ii$), the weight of each piece of gravel.

It is guaranteed that $w_1+w_2+\cdots +w_{n}w\_1\; +\; w\_2\; +\; \backslash dots\; +\; w\_n$ is a multiple of $kk$.

출력

Output the minimal number of times a stone needs to be split into two, such that all the pieces of gravel can be used to fill all the grid cells perfectly.

5 8
2 4 5 6 7

1

2 5
12 13

4