Problem:
 Score : 400 points    Problem Statement Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:   Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9) .  The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6 , respectively.       Constraints  All values in input are integers.  2 \leq N \leq 10^4  1 \leq M \leq 9  1 \leq A_i \leq 9  A_i are all different.  There exists an integer that can be formed by exactly N matchsticks under the conditions.         Input Input is given from Standard Input in the following format:  N  M  A_1  A_2  ...  A_M       Output Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.        Sample Input 1 20 4
3 7 8 4      Sample Output 1 777773  The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.       Sample Input 2 101 9
9 8 7 6 5 4 3 2 1      Sample Output 2 71111111111111111111111111111111111111111111111111  The output may not fit into a 64 -bit integer type.       Sample Input 3 15 3
5 4 6      Sample Output 3 654

Solution (Python):

n,m = map(int, input().split( ))
a = list(map(int, input().split( )))
mch = (100,2,5,5,4,5,6,3,7,6)

dp = [-1]*(n+10)
dp[0] = 0
for i in range(n+1):
    for aj in a:
        if dp[i-mch[aj]]>=0:
            dp[i] = max(dp[i], dp[i-mch[aj]]*10+aj)
print(dp[n])

Solution (Python):

ch={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

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

dp=[-1 for _ in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    res=-1
    for x in a:
        if i-ch[x]>=0:
            res=max(res,dp[i-ch[x]]*10+x)
    dp[i]=res
    
print(dp[n])

Solution (Python):
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]



def maxnum(*args):
    maxn = args[0]
    for i in range(1, len(args)):
        if len(maxn) != len(args[i]):
            if len(args[i]) > len(maxn):
                maxn = args[i]
        else:
            maxn = max(maxn, args[i])
    return maxn



nmatch = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [""] + [None] * N
for i in range(1, N + 1):
    maxn = ""
    for a in A:
        if i - nmatch[a] >= 0 and dp[i - nmatch[a]] != None:
            maxn = maxnum(maxn, dp[i - nmatch[a]] + str(a), str(a) + dp[i - nmatch[a]])
            dp[i] = maxn

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1]*(N+1)
dp[0]=0  
for i in range(N+1):
    for j in A:
        if i + B[j] <= N:
            dp[i+B[j]]= max(dp[i]*10+j, dp[i+B[j]])
print(dp[N])

Solution (Python):
n,_,*a=map(int,open(0).read().split())
ref={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-float('inf')]*(n+9)
for i in range(n+1):
	for x in a:
		if dp[i]<dp[i-ref[x]]*10+x:
			dp[i]=dp[i-ref[x]]*10+x
print(dp[n])

Solution (Python):
N,M=list(map(int,input().split()))
A=sorted(list(map(int,input().split())),reverse=True)
C=[-1,2,5,5,4,5,6,3,7,6]
DP=[[0 if j==0 else -1 for i in range(M)] for j in range(N+1)]
for i in range(N+1):
  for j in range(M):
    if(j>0):
      DP[i][j]=max(DP[i][j],DP[i][j-1]);
    if(i-C[A[j]]>=0 and DP[i-C[A[j]]][j]!=-1):
      DP[i][j]=max(DP[i][j],DP[i-C[A[j]]][j]*10+A[j]);
    if(j>0 and i-C[A[j]]>=0 and DP[i-C[A[j]]][j-1]!=-1):
      DP[i][j]=max(DP[i][j],DP[i-C[A[j]]][j-1]*10+A[j]);
print(DP[N][M-1])

Solution (Python):
N, M, *A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
A.sort(reverse=True)
cls = {ls[a] for a in A}
cls = sorted(list(cls))
dp = [-float('inf')]*(N+10)
dp[0] = 0
for i in range(1,N+1):
  dp[i] = max(dp[i-c]+1 for c in cls)
ans = 0
M = N
for i in range(dp[N]):
  for a in A:
    c = ls[a]
    if dp[M-c]+1 == dp[M]:
      ans += a*10**(dp[N]-1-i)
      M -= c
      break
print(ans)

Solution (Python):
Q = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
 
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
 

dp = [-1] * (N + 1)
dp[0] = 0
 
for a in A:
    for i in range(Q[a], N + 1):
        if dp[i - Q[a]] >= 0:
            dp[i] = max(dp[i], dp[i - Q[a]] + 1)
            
 

ans = ''
 

A.sort(reverse=True)
 
i = N
while i:
    for a in A:
        if i - Q[a] >= 0 and dp[i - Q[a]] == dp[i] - 1:
            ans += str(a)
            i -= Q[a]
            break
 
print(ans)

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

d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
c = [(i, d[i]) for i in A]
minpos = min(c, key=lambda x:x[1])[1]

dp = [0] * (N+1)
digit = [0] * (N+1)

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0 or 0<i-cost<minpos: continue
        a = dp[i]
        b = dp[i-cost] + n * (10**(digit[i-cost]))
        if a<b:
            dp[i] = b
            digit[i] = digit[i-cost] + 1

print(dp[N])

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

d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

c = [(i, d[i]) for i in A]
minpos = min(c, key=lambda x:x[1])[1]

dp = [0] * (N+1)
digit = [0] * (N+1)

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0 or 0<i-cost<minpos: continue
        a = dp[i]
        b = dp[i-cost] + n * (10**(digit[i-cost]))
        if a<b:
            dp[i] = b
            digit[i] = digit[i-cost] + 1

print(dp[N])

Solution (Python):
from copy import deepcopy
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    l = [2,5,5,4,5,6,3,7,6]
    d = {}
    for i in A:
        if l[i-1] not in d:
            d[l[i-1]] = i
        else:
            if d[l[i-1]] < i:
                d[l[i-1]] = i
    d3 = {}
    for i in d:
        d3[d[i]] = i
    d2 = list(d)
    d2.sort()
    s = [[[-1] * (len(d2)) for _ in range(len(d2))] for _ in range(N+1)]
    dp = [[0] * (len(d2)) for _ in range(N+1)]
    for w in range(N+1):
        if w % d2[0] == 0:
            dp[w][0] = w // d2[0]
            s[w][0] = [0] * (len(d2))
            s[w][0][0] = w // d2[0]
    for i in range(1, len(d2)):
        for w in range(N+1):
            if w < d2[i]:
                continue
            elif max(dp[w-d2[i]]) > 0:
                x = dp[w-d2[i]].index(max(dp[w-d2[i]]))
                if dp[w][i-1] > dp[w-d2[i]][x] + 1:
                    dp[w][i] = dp[w][i-1]
                    s[w][i] = deepcopy(s[w][i-1])
                else:
                    dp[w][i] = dp[w-d2[i]][x] + 1
                    s[w][i] = deepcopy(s[w-d2[i]][x])
                    s[w][i][i] += 1
            elif w == d2[i]:
                dp[w][i] = 1
                s[w][i] = [0] * len(d2)
                s[w][i][i] = 1
            else:
                dp[w][i] = dp[w][i-1]
                s[w][i] = deepcopy(s[w][i-1])
    maxn = 0
    for i in s[-1]:
        if sum(i) <= 0:
            continue
        qq = []
        for j,v in enumerate(i):
            if v > 0:
                qq.append((d[d2[j]],v))
        qq.sort(key=lambda x:x[0], reverse=True)
        r = ''
        for k in qq:
            r += str(k[0]) * k[1]
        if int(r) > maxn:
            maxn = int(r)
    print(maxn)
main()

Solution (Python):
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))


A.sort(reverse=True)
s = set()
candidates = [] 
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])


dp = [-1] * (N+1)
dp[0] = 0
for i in range(N+1):
  for a, n in candidates:
    if i >= n and dp[i-n]>=0:
      dp[i] = max(dp[i], dp[i-n]+1)

ans = ''
idx = N
digit = dp[N]
while digit:
  for a, n in candidates:
    if idx - n >= 0 and dp[idx-n] == dp[idx]-1:
      ans += str(a)
      digit -= 1
      idx -= n
      break

print(int(ans))

Solution (Python):
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))


A.sort(reverse=True)
s = set()
candidates = [] 
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])


dp1 = [0] * (N+1)
dp2 = [-1] * (N+1)
d = {}
for a, n in candidates:
  if n <= N:
    dp1[n] = 1
    dp2[n] = 0
    d[n] = a

for i in range(N+1):
  for a, n in candidates:
    if i >= n and dp1[i-n]:
      if dp1[i] < dp1[i-n] + 1:
        dp1[i] = dp1[i-n] + 1
        dp2[i] = i-n

ans = []
idx = N
while idx:
  next_idx = dp2[idx]
  ans.append(d[idx - next_idx])
  idx = next_idx

ans.sort(reverse=True)
print(''.join(list(map(str, ans))))

Solution (Python):
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))


A.sort(reverse=True)
s = set()
candidates = [] 
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])


dp1 = [0] * (N+1)
dp2 = [-1] * (N+1)
d = {}
for a, n in candidates:
  if n <= N:
    dp1[n] = 1
    dp2[n] = 0
    d[n] = a

for i in range(N+1):
  for a, n in candidates:
    if i >= n and dp1[i-n]:
      if dp1[i] < dp1[i-n] + 1:
        dp1[i] = dp1[i-n] + 1
        dp2[i] = i-n

ans = []
idx = N
while idx:
  next_idx = dp2[idx]
  ans.append(d[idx - next_idx])
  idx = next_idx

ans.sort(reverse=True)
print(''.join(list(map(str, ans))))

Solution (Python):
def check(i):
    global kmax,nmax
    cnt = 0
    for j in range(i):
        cnt += K[j]*B[j]
    if sum(B[:i])+(N-cnt)//K[i]<kmax:
        return
    for k in range((N-cnt)//K[i],-1,-1):
        if cnt+K[i]*k==N:
             if kmax<=sum(B[:i])+k:
                    kmax = sum(B[:i])+k
                    B[i] = k
                    num = ""
                    for j in range(len(K)):
                        num += str(D[j])*B[K.index(C[D[j]])]
                    num = int(num)
                    nmax = max(nmax,num)
        else:
            if i<len(K)-1:
                B[i] = k
                check(i+1)
            else:
                B[i] = 0
                return
C = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {}
for i in range(M):
    a = A[i]
    k = C[a]
    if k not in G:
        G[k] = 0
    if a>G[k]:
        G[k] = a
K = sorted(list(G.keys()))
D = sorted(list(G.values()),reverse=True)
B = [0 for _ in range(len(K))]
kmax = 0
nmax = 0
check(0)
print(nmax)

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
weight=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0]=0
for i in range(N+1):
    for a in A:
        if i+weight[a]<N+1:
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)
print(dp[N])

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[-1, -1] for i in range(n+1)]

dp[0] = [0, 0]
for i in range(1, n+1):
    for ai in a:
        ci = c[ai]
        if i - ci >= 0 and dp[i-ci][0] != -1:
            if dp[i][0] < dp[i-ci][0] + 1:
                dp[i] = [dp[i-ci][0] + 1, ai]
i = n
ans = []
while i > 0:
    ai = dp[i][1]
    ans.append(ai)
    i -= c[ai]
print("".join(map(str, ans)))

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[-1, -1] for i in range(n+1)]

dp[0] = [0, 0]
for i in range(1, n+1):
    for ai in a:
        ci = c[ai]
        if i - ci >= 0 and dp[i-ci][0] != -1:
            if dp[i][0] < dp[i-ci][0] + 1:
                dp[i] = [dp[i-ci][0] + 1, ai]
i = n
ans = []
while i > 0:
    ai = dp[i][1]
    ans.append(ai)
    i -= c[ai]
ans.sort(reverse=True)
print("".join(map(str, ans)))

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[-1, -1] for i in range(n+1)]
dp[0] = [0, 0]
for i in range(1, n+1):
    for ai in a:
        ci = c[ai]
        if i - ci >= 0 and dp[i-ci] != -1:
            if dp[i][0] < dp[i-ci][0] + 1:
                dp[i] = [dp[i-ci][0] + 1, ai]
i = n
ans = []
while i > 0:
    ai = dp[i][1]
    ans.append(ai)
    i -= c[ai]
ans.sort(reverse=True)
print("".join(map(str, ans)))

Solution (Python):
d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

inf = 10**9
dp = [-inf]*(N+1)
dp[0] = 0


for a in A:
    for j in range(d[a], N + 1):
        dp[j] = max(dp[j], dp[j - d[a]] + 1)

ans = ""
remain = dp[N]
match = N
while match > 0:
    for a in A:
        if match - d[a] < 0:
            continue
        if dp[match - d[a]] == remain - 1:
            ans += str(a)
            match -= d[a]
            remain -= 1
            break

print(ans)

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A.sort(key=lambda x: -x)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if X < 0: return -(1000000007)
    if memo[X] != None: return memo[X]
    
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

Solution (Python):

N, M = map(int, input().split())
A = list(map(int, input().split()))
numbers = [0,2,5,5,4,5,6,3,7,6]


dp = ["-" for i in range(11000)]
dp[0] = ""

def cal(x, y):
  lenx = len(x)
  leny = len(y)
  
  if lenx > leny:
    return x
  if leny > lenx:
    return y
  
  return max(x, y)

for i in range(N):
  if dp[i] == "-": 
    continue

  for j in range(M):
    num = numbers[A[j]]
    dp[i+num] = cal(dp[i] + str(A[j]), dp[i+num])

print(dp[N])

Solution (Python):
n,m = map(int,input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
a = list(map(int,input().split()))
dp = [-1 for _ in range(n+1)]
dp[0] = 0
for i in range(n+1):
  if dp[i] == -1: continue
  for j in a:
    if i+cost[j] <= n:
      dp[i+cost[j]] = max(dp[i+cost[j]], dp[i]*10+j)
print(dp[-1])

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

def main():
    N,M = map(int,input().split())
    p = {1:2,7:3,4:4,5:5,3:5,2:5,9:6,6:6,8:7}
    a = list(map(int,input().split()))
    INF = float("inf")
    dp = [-INF for _ in range(N+1)]
    dp[0] = 0
    for i in range(N):
        for j in a:
            if i+p[j] <= N:
                dp[i+p[j]] = max(dp[i+p[j]],dp[i]+1)
    
    dp.reverse()
    use = []
    for i in a:
        use.append((i,p[i]))
        
    use.sort(key=lambda x:(-x[0],-x[1]))
    ans = []
    now = 0
    while now < N:
        for num,i in use:
            if (now+i <= N and dp[now+i] == dp[now]-1):
                ans.append(str(num))
                now += i
                break
    print("".join(ans))
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys

def get():
	return [int(x) for x in sys.stdin.readline().rstrip().split(" ")]

N, M = get()
A = get()

tukaukazu = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

memo = [0 for x in range(N + 1)]

def search(n):
	if n < 0:
		return None
	else:
		return memo[n]

for n in range(1, N + 1):
	answer = None
	for d in A:
		senzinnnotie = search(n - tukaukazu[d])
		if senzinnnotie is not None:
			candidate = senzinnnotie * 10 + d
			if (answer is None) or (candidate > answer):
				answer = candidate
	memo[n] = answer

print(search(n))

Solution (Python):

"""
個数無制限ナップザック
大小判定は和が大きいほう→同じなら桁で比較していって先に大きくなった方
"""

N,M = map(int,input().split())

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

lis = [[0] * 10 for i in range(N+1)]
able = [False] * (N+1)
able[0] = True

nums = [0,2,5,5,4,5,6,3,7,6]

for i in A:

    for j in range(N):

        if able[j] and j+nums[i] <= N:

            if not able[j+nums[i]]:
                able[j+nums[i]] = True
                
                for k in range(10):
                    lis[j+nums[i]][k] = lis[j][k]

                lis[j+nums[i]][i] += 1

            else:

                flag = False

                if sum(lis[j+nums[i]]) < sum(lis[j]) + 1:
                    flag = True

                elif sum(lis[j+nums[i]]) == sum(lis[j]) + 1:

                    cp = lis[j].copy()
                    cp[i] += 1

                    for k in range(9,0,-1):

                        if lis[j+nums[i]][k] < cp[k]:
                            flag = True
                            break

                        elif lis[j+nums[i]][k] > cp[k]:
                            break


                if flag:
                    for k in range(10):
                        lis[j+nums[i]][k] = lis[j][k]
                    lis[j+nums[i]][i] += 1


ans = []

for i in range(9,0,-1):

    for j in range(lis[-1][i]):
        ans.append(i)

print ("".join(map(str,ans)))

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

dp = [-1] * (n+1)
dp[0] = 0
cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for i in range(n+1):
    if dp[i] == -1: continue
    for a in A:
        
        if i+cost[a] <= n:
            dp[i+cost[a]] = max(dp[i+cost[a]], dp[i]*10+a)

print(dp[-1])

Solution (Python):
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
    
a.sort(reverse=True)



dp=[0]*(n+1)



for i in range(m):

    
    for j in range(n+1):
        
        if j==0 or dp[j]!=0:
        
            if j+a[i][1]<=n:
                
                
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])


print(dp[n])

Solution (Python):
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
    
a.sort(reverse=True)



dp=[0]*(n+1)


for i in range(m):

    for j in range(n+1):
        if j==0 or dp[j]!=0:
        
            if j+a[i][1]<=n:
                
                
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])


print(dp[n])

Solution (Python):
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
    
a.sort(reverse=True)



dp=[0]*(n+1)


for i in range(m):

    for j in range(n+1):
        if j==0 or dp[j]!=0:
        
            if j+a[i][1]<=n:
                
                
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])


print(dp[n])

Solution (Python):
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
    
a.sort(reverse=True)
tuple(a)


dp=[0]*(n+1)


for i in range(m):
    for j in range(n+1):
        if j==0 or dp[j]!=0:
        
            if j+a[i][1]<=n:
                
                
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])


print(dp[n])

Solution (Python):
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
a.sort(reverse=True)


dp=[0]*(n+1)


for i in range(m):
    for j in range(n+1):
        if j==0 or dp[j]!=0:
        
            if j+a[i][1]<=n:
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])


print(dp[n])

Solution (Python):
m = [0,2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
for i in range(len(A)-1, 0, -1):
    for j in range(i-1, -1, -1):
        if m[A[i]] == m[A[j]]:
            del A[i]
            break

dp = [-1] * (N+1)
dp[0] = 0

for i in range(N):
    if dp[i]==-1: continue
    for j in range(len(A)):
        ind = i + m[A[j]]
        if ind <= N:
            dp[ind] = max(dp[ind], dp[i] * 10 + A[j])

print(dp[-1])

Solution (Python):
import sys
import copy

sys.setrecursionlimit(10**6)

m = [0,2,5,5,4,5,6,3,7,6]

def a_le_b(a, b):
    la, lb = len(a), len(b)
    if la == lb:
        for i in range(la):
            if a[i] < b[i]:
                return True
            elif a[i] > b[i]:
                return False
        return True
    return la < lb

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
for i in range(len(A)-1, 0, -1):
    for j in range(i-1, -1, -1):
        if m[A[i]] == m[A[j]]:
            del A[i]
            break

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

for i in range(N):
    if len(dp[i])==0 and i != 0: continue
    x = copy.copy(dp[i]) + [0]
    
    for j in range(len(A)):
        ind = i + m[A[j]]
        if ind <= N:
            x[-1] = A[j]
            if a_le_b(dp[ind], x):
                dp[ind] = copy.copy(x)

print(''.join(map(str, dp[-1])))

Solution (Python):
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
a.sort(reverse=True)
dp=[0]*(n+1)
for i in range(m):
    for j in range(n+1):
        if j==0 or dp[j]!=0:
            if j+a[i][1]<=n:
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
print(dp[n])

Solution (Python):
N,M = map(int,input().split())
A = list(map(int,input().split()))
num = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

def lenmax(a,b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    return max(a,b)

dp = ['-' for i in range(10**4+10)]
dp[0] = ''
for i in range(N+1):
    if dp[i] == '-':
        continue
    for a in A:
        dp[i+num[a]] = lenmax(dp[i+num[a]],dp[i]+str(a))
print(dp[N])

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

match = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

dp = ["-" for _ in range(11000)]
dp[0] = ""


def _max(a, b):
    if len(a) > len(b):
        return a
    if len(a) < len(b):
        return b
    return max(a, b)


for i in range(N+1):
    if dp[i] == "-":
        continue
    for a in A:
        dp[i+match[a]] = _max(dp[i+match[a]], dp[i]+str(a))

print(dp[N])

Solution (Python):
import resource
import sys
sys.setrecursionlimit(20000)
f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(int, input().split()))

memo = [-1]*10100


def dp(i):
    
    if i < 0:
        return - 10 ** 100000
    if not (0 <= i and i < 10100):
        print(-1)
        exit()
    if memo[i] != -1:
        return memo[i]
    if i == 0:
        return 0
    ret = -10**100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))

Solution (Python):
import resource
import sys
sys.setrecursionlimit(20000)
f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(int, input().split()))

memo = ["-1"] * 10100


def MAX(x, y):
    if y[0] != '
        return y
    else:
        return x


def dp(i):
    
    if i < 0:
        return "

    if memo[i] != "-1":
        return memo[i]

    if i == 0:
        return ""

    ret = "
    for x in a:
        ret = MAX(ret, dp(i - f[x]) + str(x))
    memo[i] = ret
    return ret


print(dp(n))

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[2,5,5,4,5,6,3,7,6]


dp=[0]*(N+10)
for j in range(M):
    need=B[A[j]-1]
    dp[need]=max(dp[need],A[j])

for i in range(1,N+1):
    for j in range(M):
        need=B[A[j]-1]
        if i-need>=0:
            if dp[i-need]:
                dp[i]=max(dp[i], dp[i-need]*10+dp[need])
            
print(dp[N])

Solution (Python):
import queue
from collections import defaultdict
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
ma=[2,5,5,4,5,6,3,7,6]
BA=[[0,0] for _ in range(M)] 
for i in range(M):
    BA[i][1]=-1*A[i]
    BA[i][0]=ma[A[i]-1]
    
BA.sort()


can=[]
ii=0
while ii <len(BA):
    if BA[ii][0] in can:
        BA.pop(ii)
    else:
        can.append(BA[ii][0])
        ii+=1
M=len(BA)

diff=[0]*M
for i in range(M):
    diff[i]=BA[i][0]-BA[0][0]
    BA[i][1]=BA[i][1]*-1

fi=BA[0]



    
p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*10


def set_to_num(L):
    ans=0
    for i in range(len(L)):
        ans+=L[i]*p[i]
    return ans


def make_set(temp,L):
    ori=copy.deepcopy(temp)
    for i in range(len(L)):
        ori[i]=L[i]
    ori.sort()
    return ori
    


def make_h(L):
    h=0
    for i in range(len(L)):
        h+=p[i]*L[i]
    return h
    
    
ans=-1
Max_dig=N//fi[0]

for d in range(Max_dig):
    dig=Max_dig-d
    rem=N-fi[0]*dig
    temp=[fi[1]]*dig
    dd = defaultdict(int)
    q=queue.Queue()
    q.put((rem,[]))
    
    while not q.empty():
        rem2,L=q.get()
        if rem2==0:
            
            LLL=make_set(temp,L)
            
            ans=max(ans,set_to_num(LLL))
        else:
            for i in range(1,M):
                if rem2>=diff[i]:
                    LL=copy.deepcopy(L)
                    LL.append(BA[i][1])
                    if len(LL)<=len(temp):
                        LL.sort()
                        h=make_h(LL)
                        if dd[h]==0:
                            q.put((rem2-diff[i],LL))
                            dd[h]=1
    if ans!=-1:
        break
        
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
INF = 10 ** 8

for i in range(9):
    if i + 1 not in A:
        num[i] = INF

dp = [-INF] * (N + 1)
dp[0] = 0

for i in range(1, N + 1):
    for j in range(9):
        k = i - num[j]
        if k >= 0:
            dp[i] = max(dp[i], dp[k] + 1)

ans = ''
rest = N
for i in range(dp[N]):
    t = 0
    for j in range(8, -1, -1):
        k = rest - num[j]
        if k >= 0:
            if dp[rest - num[j]] == dp[rest] - 1:
                t = max(t, j + 1)
    ans += str(t)
    rest -= num[t - 1]

print(int(ans))

Solution (Python):
N,M=[int(x) for x in input().split()]
X=[0,2,5,5,4,5,6,3,7,6]


A=[int(x) for x in input().split()]



ANS=[0]
for i in range(1,N+1):
	ans=0
	for j in A:
		if i==X[j]:
			ans=max(j,ans)
		elif i>=X[j]:
			temp=ANS[i-X[j]]
			if temp!=0:

				ans=max(ans,10*temp+j)
		
		
	ANS.append(ans)
print(ANS[-1])

Solution (Python):

import math
import heapq
import bisect
import numpy as np


number = [0,2,5,5,4,5,6,3,7,6]

N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

dp = [-1]*(N+1)
dp[0] = 0
for i in range(N+1):
    for a in A:
        if i-number[a] >= 0:
            if dp[i-number[a]] >= 0:
                dp[i] = max(dp[i], dp[i-number[a]]*10+a)

print(dp[N])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    A = LI()
    num2match = {
        1: 2,
        2: 5,
        3: 5,
        4: 4,
        5: 5,
        6: 6,
        7: 3,
        8: 7,
        9: 6,
    }
    dp = ['' for _ in range(N+1)]
    for a in A:
        match_need = num2match[a]
        if 0 <= match_need <= N:
            dp[match_need] = max(str(dp[match_need]), str(a))
    for i in range(N+1):
        for a in A:
            match_need = num2match[a]
            if i - match_need > 0:
                if dp[i-match_need] == '':
                    continue
                old = dp[i]
                new = str(a) + dp[i-match_need]
                if len(old) > len(new):
                    dp[i] = old
                elif len(new) > len(old):
                    dp[i] = new
                else:
                    dp[i] = max(old, new)
    print(dp[N])
main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
A = LI()
L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
match_set = {L[a] for a in A}
dp = [-INF] * (n + 1)
dp[0] = 0
for i in range(n + 1):
    for s in match_set:
        if i - s >= 0:
            dp[i] = max(dp[i - s] + 1, dp[i])

D = defaultdict(int)
for a in A:
    D[L[a]] = max(D[L[a]], a)

kv = sorted(D.items())
digit = dp[n]
ans = ''
while n:
    max_num = 0
    for cost, num in kv:
        if n - cost >= 0 and dp[n - cost] == digit - 1:
            if num > max_num:
                max_num = num
                c = cost
    ans += str(max_num)
    digit -= 1
    n -= c


print(ans)

Solution (Python):
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
cs = {m: costs[m - 1] for m in a}
INF = 10 ** 9
dp = [0]

for i in range(1, n + 1):
    dp.append(max(
        [dp[i - c] if i - c >= 0 else -INF for c in cs.values()]
    ) + 1)

digits = list(cs.keys())
digits.sort(reverse=True)
num = n
ans = []
for _ in range(dp[n]):
    for digit in digits:
        if num >= cs[digit] and dp[num - cs[digit]] != -INF and dp[num - cs[digit]] == dp[num] - 1:
            ans.append(str(digit))
            num -= cs[digit]
            break
print("".join(ans))