불쌍한 Bessie는 국경 너머 바로 있는 Slobbovia 편의점에 취직했습니다. USA와 다른 동전이며 값이 매일 바뀝니다!

Slobbovia 고객에게 최적 거스름돈을 주세요. 액면가 $N$종류($1 \le N \le 10$)로 $C$센트($1 \le C \le 1000$)를 만듭니다. 모든 테스트는 주어진 동전으로 됩니다.

50, 25, 10, 5, 1 다섯 종류면 93센트의 최소 동전은 $1 \times 50$, $1 \times 25$, $1 \times 10$, $1 \times 5$, $3 \times 1$로 총 7개입니다.

얼마나 어렵겠어요? 마지막 두 테스트는 까다롭습니다.

입력

표준 입력을 읽습니다.

1번 줄: 공백으로 구분된 정수 $C$, $N$.

$2..N+1$번 줄: 줄마다 서로 다른 정수인 사용 가능한 동전 값.

출력

표준 출력에 씁니다.

1번 줄: $C$센트를 만드는 최소 동전 수인 정수 하나.

예제

입력 1

93 5
25
50
10
1
5

출력 1

7

출처: USACO 2007년 1월 브론즈