시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 25 4 4 18.182%

문제

민식이는 새로운 퍼즐을 선물로 받았다. 보드는 다양한 길이의 여러개의 조각으로 이루어져 있다. 각 조각은 보드와 같은 폭을 가지고 있다. 퍼즐의 목표는 다른 조각을 더 이상 놓을 수 없게 적은 수의 조각을 놓는 것이다. 조각은 보드의 모서리에 걸치면 안되고, 각도를 비틀어도 안된다. 모든 조각은 서로 겹치면 안된다. 그러나, 조각의 모서리는 서로 닿아도 된다. 조각과 조각 사이의 거리와, 조각과 보드의 모서리 사이의 거리는 꼭 정수가 아니어도 된다.

보드의 길이와 각 조각의 길이가 주어질 때, 퍼즐의 목표를 수행하는 프로그램을 작성하시오.
 

입력

첫째 줄에 L과 조각의 수 N이 주어진다. L은 1,000보다 작거나 같은 자연수이고, N은 30보다 작거나 같은 자연수이다. 둘째 줄에는 각 조각의 길이가 주어진다. 각 조각의 길이는 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

36 5
1 1 5 5 5

예제 출력

4

힌트

출처