Combinatorial - Coin Changing Problem

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

コイン問題

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

入力

n m
c1 c2 ... cm

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

出力

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

制約

  • 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

      解説