可哀想な 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 月ブロンズ