output_description: Print the minimum number of coins in a line.
input_description: n m
      d1 d2 ... dm
      
  
  Two integers n and m are given in the first line. The available denominations
  are given in the second line.
attempt: def resolve():
      Nyens, Mtypes = map(
          int, input().split()
      )  # N円をM種類のコインで最小枚数で払うという問題
      types = list(map(int, input().split()))  # 何円玉があるかのリスト
  
      def knapsack(Nyens, Mtypes, types):
          # dp[i][j]:i種類目までのコイン限定でj円払うのに必要な最小枚数
          # 最小で無限枚必要として初期化
          dp = [[float("inf")] * (Nyens + 1) for _ in range(Mtypes + 1)]
  
          # 0円は0枚で払える
          for ii in range(Mtypes):
              dp[ii][0] = 0
  
          for i in range(Mtypes):
              for j in range(Nyens + 1):
                  if j >= types[i]:  # 最小枚数更新の可能性
                      dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - types[i]] + 1)
                  else:  # 可能性なし
                      dp[i + 1][j] = dp[i][j]
  
          return dp[Mtypes][Nyens]
  
      print(knapsack(Nyens, Mtypes, types))
  
  
  resolve()
  
problem_description: Coin Changing Problem
  
    
  
  Find the minimum number of coins to make change for n cents using coins of
  denominations d1, d2,.., dm. The coins can be used any number of times.
samples: [{"input": "55 4\n    1 5 10 50", "output": "2"}, {"input": "15 6\n    1 2 7 8 12 50", "output": "2"}, {"input": "65 6\n    1 2 7 8 12 50", "output": "3"}]