시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB116201415.054%

문제

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

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

입력

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

출력

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

예제 입력 1

36 5
1 1 5 5 5

예제 출력 1

4

예제 입력 2

9 2
1 8

예제 출력 2

1

예제 입력 3

37 5
1 1 5 5 5

예제 출력 3

5

예제 입력 4

18 6
2 2 2 9 9 10

예제 출력 4

2

예제 입력 5

1 3
2 3 4

예제 출력 5

0

예제 입력 6

703 18
73 76 90 42 84 13 57 88 80 45 80 1 78 41 73 40 97 42

예제 출력 6

7

출처