コイン問題

額面がc₁, c₂,..., c_m　円の　m　種類のコインを使って、 n 円を支払うときの、コインの最小の枚数を求めて下さい。各額面のコインは何度でも使用することができます。

入力

n m
c1 c2 ... cm

１行目に整数 n と整数 m が１つの空白区切りで１行に与えられます。２行目に各コインの額面が１つの空白区切りで１行に与えられます。

出力

コインの最小枚数を１行に出力してください。

制約

• 1 ≤ n ≤ 50,000
• 1 ≤ m ≤ 20
• 1 ≤ 額面 ≤ 10,000
• 額面はすべて異なり、必ず1を含む。

入出力例

入力例 1

15 6
1 2 7 8 12 50

出力例 1

2

入力例 2

65 6
1 2 7 8 12 50

出力例 2

3

Note

      解説      

---