조각 놓기

민식이는 길이 L인 보드와 여러 개의 조각을 가지고 있다. 모든 조각의 폭은 보드와 같고, 각 조각은 주어진 길이를 가진다.

목표는 가능한 적은 수의 조각을 보드 위에 놓아서, 아직 놓지 않은 어떤 조각도 더 이상 보드에 추가로 놓을 수 없게 만드는 것이다. 조각은 보드 밖으로 튀어나가면 안 되고, 회전할 수 없으며, 서로 겹칠 수 없다. 다만 조각의 끝점끼리 맞닿거나 조각이 보드의 끝에 닿는 것은 허용된다. 조각 사이의 거리와 조각과 보드 끝 사이의 거리는 정수일 필요가 없다.

보드의 길이와 각 조각의 길이가 주어질 때, 목표를 달성하기 위해 놓아야 하는 조각 수의 최솟값을 구하시오.

첫째 줄에 보드의 길이 L과 조각의 수 N이 주어진다.

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

둘째 줄에는 각 조각의 길이가 주어진다. 각 조각의 길이는 100 이하의 자연수이다.

목표를 달성하기 위해 놓아야 하는 조각 수의 최솟값을 출력한다.

처음부터 놓을 수 있는 조각이 하나도 없다면 0을 출력한다.