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

문제

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

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

입력

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

출력

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

예제 입력 1

36 5
1 1 5 5 5

예제 출력 1

4

출처