Problem:
Coin Changing Problem Find the minimum number of coins to make change for n cents using coins of denominations d 1 , d 2 ,.., d m . The coins can be used any number of times. Input  n  m  d 1  d 2 ... d m  Two integers n and m are given in the first line. The available denominations are given in the second line. Output Print the minimum number of coins in a line. Constraints  1 ≤ n ≤ 50000  1 ≤ m ≤ 20  1 ≤ denomination ≤ 10000  The denominations are all different and contain 1.  Sample Input 1 55 4
1 5 10 50 Sample Output 1 2 Sample Input 2 15 6
1 2 7 8 12 50 Sample Output 2 2 Sample Input 3 65 6
1 2 7 8 12 50 Sample Output 3 3

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split())) 


dp = [[float('inf')]*(n+1) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    for x in range(n+1):
        dp[i+1][x] = dp[i][x]

        if x -c[i]>= 0:
            dp[i+1][x] = min(dp[i+1][x - c[i]] + 1, dp[i][x])
print(dp[m][n])

Solution (Python):
INF = 10 ** 18
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(m):
    for j in range(c[i], n + 1):
        dp[j] = min(dp[j], dp[j - c[i]] + 1)

print(dp[n])

Solution (Python):
N,M=list(map(int,input().split()))
C=list(map(int,input().split()))
dp=[0]+[50001 for _ in range(N)]


for i in range(M):
  for j in range(C[i],N+1):
    if C[i] > N:
      break
    elif dp[j-C[i]] != 50001:
      dp[j] = min(dp[j],dp[j-C[i]] + 1)

print(dp[N])

Solution (Python):
n,m=map(int,input().split())
C=list(map(int,input().split()))
dp=[0]*(n+1)
dp[0]=1

for i in range(m):
    for j in range(n+1):
        if dp[j]!=0:
            if j+C[i]<=n:
                if dp[j+C[i]]==0:
                    dp[j+C[i]]=dp[j]+1
                else:
                    dp[j+C[i]]=min(dp[j]+1,dp[j+C[i]])
    
print(dp[n]-1)

Solution (Python):
n,m = map(int,input().split())
C = list(map(int,input().split()))
dp = [float('inf') for _ in range(n+1)]

for i in range(n+1):
    for c in C:
        if i + c  <= n:
            dp[i+c] = min(dp[i+c],dp[i]+1) if dp[i] != float('inf') else 1
print(dp[n])

Solution (Python):
n,m= map(int,input().split())
c= list(map(int,input().split()))
inf=60000
dp=[inf]*50010
dp[0]=0
dp[1]=1
for i in range(2,n+1):
    for j in c:
        if i-j>=0:
            dp[i]=min(dp[i-j]+1, dp[i])
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp =[[float("inf")] * (n+1) for _ in range(m+1)]
dp[0][0] = 0

for i in range(m):
    for j in range(n+1):
        if j >= c[i]:
            dp[i+1][j] = min(dp[i+1][j-c[i]] + 1, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[m][n])

Solution (Python):
n,m = map(int,input().split())
coins = list(map(int,input().split()))

inf = 10 ** 6

dp = [inf] * (n + 1)
dp[0] = 0

for c in range(m):
  for v in range(n + 1):
    if v >= coins[c]:
      dp[v] = min(dp[v - coins[c]] + 1,dp[v])
    else:
      dp[v] = dp[v]
      
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
C = list(map(int, input().split()))

N = [float('inf')] * (50000 + 1)
N[0] = 0
for i in range(1, 50000 + 1):
    for c in C:
        if i - c < 0:
            continue
        N[i] = min(N[i - c] + 1, N[i])

print(N[n])

Solution (Python):
INF = 10 ** 7
def main():
    N,M = map(int,input().split())
    coin = list(map(int,input().split()))
    dp = [INF] * (N + 1)
    dp[0] = 0
    for c in coin:
        for i in range(c,N + 1):
            dp[i] = min(dp[i],dp[i - c] + 1)
    print(dp[-1])
if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[[10001]*m for i in range(n)] 
dp.insert(0,[0]*m)
for i in range(m):
  for v in range(1,n+1):
    if i==0:
      dp[v][i]=v//c[i] if v%c[i]==0 else 10001
      continue
    if v<c[i]:
        dp[v][i]=dp[v][i-1]
    else:
      dp[v][i]=min(dp[v][i-1],dp[v-c[i]][i]+1)
print(dp[n][m-1])

Solution (Python):
N,M=map(int,input().split())
lists=list(map(int,input().split()))
dp=[float("inf") for i in range(N+1)]
dp[0]=0
for i in range(1,N+1):
    for num in lists:
        if i>=num:
            dp[i]=min(dp[i],dp[i-num]+1)
print(dp[N])

Solution (Python):
INF = float('inf')
N, M = map(int, input().split())
C = [int(c) for c in input().split()]
T = [[INF] * (N + 1) for _ in range(M + 1)]
for i in range(M + 1):
    T[i][0] = 0

for i in range(1, M + 1):
        for j in range(1, N + 1):
            if N + 1 < j - C[i - 1] or j - C[i - 1] < 0:
                T[i][j] = T[i - 1][j]
            else:
                T[i][j] = min(T[i - 1][j], T[i][j - C[i - 1]] + 1)

ans = []
for i in range(1, M + 1):
    ans.append(T[i][N])

print(min(ans))

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    n,m,*C = map(int, read().split())

    
    dp = [10**10] * (n+1)
    dp[0] = 0

    for c in C:
        for i in range(n+1):
            if i + c <= n:
                dp[i+c] = min(dp[i] + 1, dp[i+c])

    print(dp[n])


if __name__ == "__main__":
    main()

Solution (Python):


def solve():
    import sys

    N, M = list(map(int, sys.stdin.readline().split()))
    Cs = list(map(int, sys.stdin.readline().split()))

    dp = [float("inf") for _ in range(N+1)]  
    dp[0] = 0

    for c in Cs:
        for i in range(c, N+1):
            dp[i] = min(dp[i], dp[i-c]+1)
    print(dp[N])


if __name__ == "__main__":
    solve()

Solution (Python):
n, m = map(int, input().split())

C = list(map(int, input().split()))


dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(m):
    for j in range(n + 1):
        if j >= C[i]:
            dp[j] = min(dp[j - C[i]] + 1, dp[j])

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))

dp = [float('inf') for _ in range(n+1)]
dp[0] = 0

for i in range(n):
    for money in a:
        next_money = i + money
        if next_money > n:
            continue
        dp[next_money] = min(dp[i] + 1, dp[next_money])

print(dp[n])

Solution (Python):


















 
n,m = map(int,input().split())
c = list(map(int,input().split()))
 

dp = []
for i in range(m+100):
    tmp = [0]
    for j in range(n+99): tmp.append(float('inf'))
    dp.append(tmp)
    

for i in range(m):
  
  for j in range(n+1):
    if(j>=c[i]): 
      dp[i+1][j] = min(dp[i][j-c[i]]+1, 
                       dp[i][j],
                       dp[i+1][j-c[i]]+1)  
    else: 
      dp[i+1][j] = dp[i][j]



print(dp[m][n])

Solution (Python):
N, M = map(int, input().split())

def solve(N,M):
    dp = [[float('inf')]*(N+1) for _ in range(M+1)]
    C = list(map(int, input().split()))
    dp[0][0] = 0
    for i in range(1,M+1):
        dp[i][0] = 0
        for j in range(1,N+1):
            dp[i][j] = dp[i-1][j]
            if j>=C[i-1]:
                dp[i][j] = min(dp[i][j],dp[i][j-C[i-1]]+1)
    ans = dp[M][N]
    return ans
print(solve(N,M))

Solution (Python):
n, m = map(int, input().split())
C = list(map(int, input().split()))

def coin():
    dp = [float('inf')]*(n+1)
    dp[0] = 0
    for i in range(m):
        for j in range(C[i], n+1):
            dp[j] = min(dp[j], dp[j-C[i]]+1)
    return dp[n]

print(coin())

Solution (Python):
import sys

readline = sys.stdin.readline

def main():
    n, m = map(int, readline().split())
    c = list(map(int, readline().split()))

    maxnum = 50001
    DP = [maxnum] * (n+1)
    DP[0] = 0
    for ctmp in c:
        for j in range(ctmp, n+1):
            if DP[j-ctmp] == maxnum:
                continue
            else:
                DP[j] = min(DP[j], DP[j-ctmp] + 1)
    
    ans = DP[n]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
li_c = list(map(int, input().split()))

INF = 10**7
dp = [INF]*(50010)
dp[0] = 0
dp[1] = 1

for i in range(50001):
    for coin in li_c:
        if i+coin<50010:
            dp[i+coin] = min(dp[i]+1, dp[i+coin])
print(dp[n])

Solution (Python):
N, M = map(int, input().split())
C = list(map(int, input().split()))


dp = [[10 ** 9] * (N+1) for _ in range(M+1)]
dp[0][0] = 0
for i in range(1,M+1):
    for j in range(N+1):
        if j - C[i-1] >= 0:
            dp[i][j] = min(dp[i][j-C[i-1]]+1, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[M][N])

Solution (Python):
import sys

n, m = map(int, sys.stdin.readline().strip().split())
c = list(map(int, sys.stdin.readline().strip().split()))

dp = [float("inf") for _ in range(n+1)]
dp[0] = 0

for i in range(n+1):
    for c_i in c:
        if i - c_i >= 0:
            dp[i] = min(dp[i], dp[i - c_i] + 1)

print(dp[n])

Solution (Python):
n,m = map(int,input().split())
D = list(map(int,input().split()))

INF = 10**5
dp = [INF for i in range(n+1)]
dp[0] = 0

for i in range(n+1):
    for d in D:
        if i+d <= n:
            dp[i+d] = min(dp[i+d],dp[i]+1)
print(dp[n])

Solution (Python):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, m = MAP()
c = LIST()

price = [float("INF")] * (n+1)
price[0] = 0

for i in range(n+1):
    for j in range(m):
        if i - c[j] < 0:
            continue
        price[i] = min(price[i], price[i-c[j]] + 1)

print(price[-1])

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))

dp=[10**5]*(n+1)
dp[0]=0
dp[a[0]]=1

for i in range(n+1):
    for j in range(m):
        if i-a[j]>=0:
            dp[i]=min(dp[i],dp[i-a[j]]+1)
print(dp[-1])

Solution (Python):
N, M = map(int, input().split())
Coins = list(map(int, input().split()))

DP = [10 ** 9 for _ in range(N + 1)]
DP[0] = 0

for i in range(N):
    for c in Coins:
        if i + c <= N:
            DP[i + c] = min(DP[i + c], DP[i] + 1)

print(DP[N])

Solution (Python):
n, m = map(int, input().split())
c = [int(i) for i in input().split()]
dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    dp[i][1] = i
for j in range(1, m + 1):
    dp[0][j] = 0
    
for i in range(n + 1):
    for j in range(1, m):
        if c[j] > i:
            dp[i][j + 1] = dp[i][j]
        else:
            dp[i][j + 1] = min(dp[i][j], dp[i - c[j]][j + 1] + 1)
print(dp[n][m])

Solution (Python):
n, m = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
d = {0:0}
for i in range(1, n + 1):
    min_ = n + 1
    for j in C:
        if i - j in d:
            tmp = d[i - j] + 1
            if tmp < min_:
                min_ = tmp
    d[i] = min_
print(d[n])

Solution (Python):
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N, M = map(int, input().split())
C = list(map(int, input().split()))
MAX = 20

dp = [list(range(N+1)) for _ in range(M+1)]

for i in range(1, M+1):
    c = C[i-1]
    for j in range(N+1):
        if j-c>=0:
            dp[i][j] = min(dp[i-1][j-c]+1, dp[i-1][j], dp[i][j-c]+1)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[M][N])

Solution (Python):
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N, M = map(int, input().split())
C = list(map(int, input().split()))
MAX = 20

dp = [list(range(N+1)) for _ in range(M+1)]

for i in range(1, M+1):
    c = C[i-1]
    for j in range(N+1):
        if j-c>=0:
            dp[i][j] = min(dp[i-1][j-c]+1, dp[i-1][j], dp[i][j-c]+1)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[M][N])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m,*c = map(int,read().split())
INF = 9**9
dp = [INF] * (n+1)

dp[0] = 0
for i in range(1,n+1):
    for j in c:
        if i-j>= 0:
            dp[i] = min(dp[i],dp[i-j]+1)

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
l = list(map(int, input().split()))
dp = [10**5] * (n+1)
dp[0] = 0
for i in range(len(l)):
    m = l[i]
    for j in range(m,n+1):
        dp[j] = min(dp[j-m]+1, dp[j])
print(dp[n])

Solution (Python):
n,m = map(int,input().split())
c = [int(i) for i in input().split()]
dp = [[float("INF")]*(n+1) for _ in range(m+1)]

dp[0][0] = 0
for i in range(m):
    for yen in range(n+1):
        if yen - c[i] < 0: dp[i+1][yen] = dp[i][yen]
        else: dp[i+1][yen] = min(dp[i][yen],dp[i+1][yen-c[i]]+1)
print(dp[m][n])

Solution (Python):
n, m = map(int, input().split())
c = [0] + list(map(int, input().split()))

INF = 1 << 29


NMAX = 500000
dp = [INF] * (NMAX + 1)

dp[0] = 0

for i in range(1, m + 1):
	for j in range(c[i], n + 1):
		dp[j] = min(dp[j], dp[j-c[i]] + 1)

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
D = list(map(int, input().split()))

INF = int(1e18)


dp = [INF] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    for d in D:
        if i - d >= 0:
            dp[i] = min(dp[i], dp[i - d] + 1)
        else:
            dp[i] = dp[i]

print(dp[n])

Solution (Python):
inf = 10**9+7
mod = 10**9+7
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [[inf for j in range(n+1)]for i in range(m+1)] 
dp[0][0] = 0
for i in range(m):
    dp[i+1][0] = 0
    for j in range(n):
        if j+1-c[i] >= 0:
            dp[i+1][j+1] = min(dp[i][j+1], dp[i][j+1-c[i]]+1, dp[i+1][j+1-c[i]]+1)
        else:
            dp[i+1][j+1] = dp[i][j+1]
print(dp[m][n])

Solution (Python):
inf=10**9
n,m=map(int,input().split())
C=list(map(int,input().split()))

DP=[inf]*(n+1)
DP[0]=0
for i in range(n+1):
    for c in C:
        if 0<=i+c<=n:
            DP[i+c]=min(DP[i+c],DP[i]+1)
print(DP[n])

Solution (Python):
n,m=map(int,input().split())
coins=list(map(int,input().split()))
dp=[float('inf')]*(n+1)
dp[0]=0
for i in range(m):
    for j in range(1,n+1):
        if j>=coins[i]:
            dp[j]=min(dp[j],dp[j-coins[i]]+1)
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp = [0] * (n+1)

for i in range(1, n+1):
  dpi = 10 ** 9
  for j in range(m):
    if(i-c[j]>=0):
      tmp = dp[i-c[j]] + 1
      if(tmp < dpi):
        dpi = tmp
  dp[i] = dpi
  
  
print(dp[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




N, M = mi()
C = li()

'''

dp = dp2(float('inf'), N+1, M+1)
dp[0][0] = 0
for i in range(1, M+1):
    for j in range(N+1):
        
            
        dp[i][j] = min(dp[i-1][j], dp[i][j])
        c = C[i-1]
        if j+c <= N:
            dp[i][j+c] = min(dp[i][j]+1, dp[i-1][j+c])

print(dp[M][N])
'''


dp = [float('inf') for i in range(N+1)]
dp[0] = 0

for i in range(M):
    for j in range(N+1):
        c = C[i]
        if j+c <= N:
            dp[j+c] = min(dp[j]+1, dp[j+c])

print(dp[N])

Solution (Python):
n,m = map(int,input().split())
c = list(map(int,input().split()))
dp = [[10000000000]*m for _ in range(n+1)]
dp[0] = [0]*m

"""
m i 枚数
n j 金額

"""

for j in range(1,n+1):
  for i in range(m):
    v = c[i]
    if j >= v:
      dp[j][i] = min(dp[j][i-1],dp[j-v][i-1]+1,dp[j-v][i]+1)
    else:
      dp[j][i] = dp[j][i-1]
      
print(dp[n][m-1])

Solution (Python):
N,M = map(int, raw_input().split())
C = map(int, raw_input().split())

INF = 10**9
DP = [INF]*(N+1)
DP[0] = 0

for i in range(1, N+1):
    for c in C:
        if c <= i:
            DP[i] = min(DP[i], DP[i-c]+1)

print DP[N]

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))
inf = 10 ** 7

dp = [inf for _ in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
    for j in range(m):
        if i - c[j] >= 0:
            dp[i] = min(dp[i], dp[i-c[j]] + 1)

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
*C, = map(int, input().split())



inf = 10**10
DP = [[inf for j in range(n+1)] for i in range(m+1)]
DP[0][0] = 0
for i in range(m):
    for j in range(n+1):
        if j < C[i]:
            DP[i+1][j] = DP[i][j]
        else:
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-C[i]]+1)
print(DP[m][n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp = [[float('inf')]*50010 for _ in range(25)]
dp[0][0] = 0
for i in range(m):
    for j in range(n+1):
        if j >= c[i]:
            dp[i+1][j] = min(dp[i][j-c[i]] + 1, dp[i][j], dp[i+1][j-c[i]]+ 1)
        else:
            dp[i+1][j] = dp[i][j]

print(dp[m][n])

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    n, m = map(int, input().split())
    c = list(map(int, input().split()))

    
    dp = [float('inf')]*(n+1)
    dp[0] = 0

    for i in range(1, n+1):
        for j in range(m):
            if i>=c[j]:
                dp[i] = min(dp[i-c[j]]+1, dp[i])

    print(dp[n])

if __name__ == '__main__':
    resolve()

Solution (Python):
n, m = map(int, input().split())
coins = list(map(int, input().split()))
coins.insert(0, 0)
inf = float('inf')
dps = [[inf for _ in range(n + 1)] for _ in range(m + 1)]


for i in range(m + 1):
    dps[i][0] = 0

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if i == 1:
            dps[i][j] = j // coins[i]
            continue
        if j >= coins[i]:
            dps[i][j] = min(dps[i][j - coins[i]] + 1,
                            dps[i - 1][j - coins[i]] + 1,
                            dps[i - 1][j])
        else:
            dps[i][j] = dps[i - 1][j]
print(dps[m][n])

Solution (Python):

n, m = map(int,input().split())
c = [int(i) for i in input().split()] 

dp = [100000 for _ in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
    for j in c:
        if 0 <= i - j:
            dp[i] = min(dp[i - j] + 1, dp[i])
print(dp[n])

Solution (Python):
INF = 10**8

n, m = map(int, input().split())
c = list(map(int, input().split()))

d = [INF] * (n + 1)
d[0] = 0

for coin in c:
	for price in range(coin, n + 1):
		d[price] = min(d[price], d[price - coin] + 1)

print(d[n])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))

DP = [[100000 for _ in range(n+1)] for _ in range(m+1)]
DP[0][0] = 0

for i in range(m):
    for j in range(n+1):
        if(j >= c[i]):
            DP[i+1][j] = min(DP[i][j], DP[i+1][j-c[i]]+1)
        else:
            DP[i+1][j] = DP[i][j]

print(DP[m][n])

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))
c.sort(reverse=True)


dp=[0]
for i in range(1,n+1):
    mini=float("inf")
    for num in c:
        if i-num>=0:
            mini=min(mini,dp[i-num]+1)
    dp.append(mini)


print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [float('inf')]*(n+1)
dp[0] = 0
for i in range(m):
    for j in range(n+1):
        if j - c[i] >= 0:
            dp[j] = min(dp[j], dp[j-c[i]] + 1)

print(dp[n])

Solution (Python):
n,m=map(int,input().split())
c=list(map(int,input().split()))

dp=[[0]*(n+1) for i in range(m)]
for i in range(n+1):
    dp[0][i]=i
for j in range(m):
    dp[j][0]=0
    dp[j][1]=1
for i in range(1,m):
    for j in range(n+1):
        if(j-c[i]>=0):
            dp[i][j]=min(dp[i-1][j],dp[i][j-c[i]]+1)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[m-1][n])

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    n, m = MI()
    c = LI()
    dp = [[IINF] * (n+1) for i in range(m+1)]
    dp[0][0] = 0

    for i in range(m):
        for j in range(n+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j + c[i] <= n:
                dp[i][j+c[i]] = min(dp[i][j+c[i]], dp[i][j] + 1)
                dp[i+1][j+c[i]] = min(dp[i+1][j+c[i]], dp[i][j] + 1)
    print(dp[m][n])

if __name__ == '__main__':
    main()

Solution (Python):
if __name__ == '__main__':
	n, m = map(int, input().split())
	coin_list = list(map(int, input().split()))
	dp = [50000] * (n + 1)
	dp[0] = 0

	for coin in coin_list:
		for i in range(n - coin + 1):
			if dp[i + coin] > dp[i] + 1:
				dp[i + coin] = dp[i] + 1

	print(dp[-1])

Solution (Python):
n,m = map(int, input().split())
c = list(map(int, input().split()))
INF = 10**9
  
dp = [INF] * (n+1)
dp[0] = 0

for i in range(n+1):
  for j in range(m):
    if i >= c[j]:
      dp[i] = min(dp[i], dp[i-c[j]]+1)
  
print(dp[n])

Solution (Python):
n, m = list(map(int, input().split()))

cs = list(map(int, input().split()))
_max = 10 ** 1000

dp = [_max for _ in range(n+1)]
dp[1] = 1
dp[0] = 0

for i in range(2, n+1):
    for c in cs:
        if i-c >= 0:
            dp[i] = min(dp[i], dp[i-c]+1)

print(dp[n])

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))

dp = [[1<<60]*(N+1) for _ in range(M+1)]
dp[0][0] = 0

for i in range(M):
    for j in range(N+1):
        if A[i] <= j:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]] + 1)
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[M][N])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N,M=map(int,input().split())
    c=list(map(int,input().split()))
    dp=[[INF]*10**6 for _ in range(M+1)]
    dp[0][0]=0
    ans=INF
    for i in range(M):
        for money in range(N+1):
            dp[i+1][money]=min(dp[i+1][money],dp[i][money])
            if money-c[i]>=0:
                dp[i+1][money]=min(dp[i+1][money],dp[i][money-c[i]]+1,dp[i+1][money-c[i]]+1)
    print(dp[M][N])

if __name__ == '__main__':
    main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():

    N, W = iip()
    dp = [100000] * (100000)
    dp[0] = 0

    coins = iip(True)

    for i in coins:
        for j in range(100000):
            if j-i < 0:
                continue
            dp[j] = min(dp[j-i]+1, dp[j])

    
    print(dp[N])











def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  
    if isinstance(l, list):
        l = l[0] 
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): 
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            
            l = x

    
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                
                
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Solution (Python):
n,m=[int(j) for j in input().split()]
c=[int(j) for j in input().split()]
dp=[10**18]*(n+1)
dp[0]=0
for i in c:
    for j in range(i,n+1):
        dp[j]=min(dp[j],dp[j-i]+1)
print(dp[-1])

Solution (Python):
INF=10**30
n,m=map(int,input().split())
c=list(map(int,input().split()))
dp=[INF]*(n+10)
dp[0]=0
for i in range(1,n+1):
    for j in range(len(c)):
        if(i-c[j]<0):
            continue
        dp[i]=min(dp[i],dp[i-c[j]]+1)
print(dp[n])

Solution (Python):
n,m = map(int,input().split())
coins = sorted(list(map(int,input().split())),reverse=True)

dp = [float("inf")]*50001

dp[0] = 0

for  i in range(50001):
    for coin in coins:
        if i+coin > 50000:
            continue
        
        else:
            dp[i+coin] = min(dp[i+coin], dp[i]+1)

print(dp[n])

Solution (Python):


N, M = map(int, input().split())  
C = list(map(int, input().split()))
dp = [[10**10]*(N+1) for _ in range(M+1)]  

dp[0][0] = 0

for i in range(M):
    for j in range(N+1):
        
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        
        if j + C[i] > N:  
            continue
        
        dp[i+1][j+C[i]] = min(dp[i][j]+1, dp[i+1][j]+1)
print(dp[M][N])

Solution (Python):

def main():
    inf = 1<<29
    n,m = map(int,input().split())
    coins = list(map(int,input().split()))
    dp = [inf]*(n+1)
    dp[0] = 0
    for i in range(1,n+1):
        for j in range(m):
            if i-coins[j]<0:continue
            dp[i] = min(dp[i],dp[i-coins[j]]+1)
    print (dp[n])


if __name__ == '__main__':
    main()