410423: GYM104020 G 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 $$$8$$$, which can be filled as follows. Put the stones of weight $$$2$$$ and $$$6$$$ in the first cell. Now grind the stone of weight $$$7$$$ into two pieces of weight $$$3$$$ and $$$4$$$. Then the other two grid cells get filled by weights $$$3, 5$$$ and $$$4, 4$$$ respectively.

The input consists of:

• One line with two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq k \leq 8$$$), the number of pieces of gravel and the capacity per grid cell.
• One line with $$$n$$$ integers $$$w_1, \dots, w_n$$$ ($$$1 \leq w_i \leq 10^6$$$ for all $$$i$$$), the weight of each piece of gravel.

It is guaranteed that $$$w_1 + w_2 + \dots + w_n$$$ is a multiple of $$$k$$$.

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