Placing Puzzle Pieces

Minsik has a board of length L and several puzzle pieces. Every piece has the same width as the board, and each piece has its own length.

The goal is to place as few pieces as possible on the board so that no unplaced piece can be added to the board anymore. A piece may not stick out of the board, may not be rotated, and may not overlap another piece. Endpoints may touch each other or the ends of the board. Distances between pieces, and between a piece and an end of the board, do not have to be integers.

Given the board length and the length of each piece, compute the minimum number of pieces that must be placed to achieve the goal.

The first line contains the board length L and the number of pieces N.

• 1 <= L <= 1000
• 1 <= N <= 30

The second line contains the lengths of the pieces. Each piece length is a positive integer at most 100.

Print the minimum number of pieces that must be placed to achieve the goal.

If no piece can be placed from the start, print 0.