BAPC22-064.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.