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):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = sorted(LI())

    t = [9,2,5,5,4,5,6,3,7,6]
    d = {}
    for c in a:
        d[t[c]] = c

    dp = [0] * (n+10)
    for i in range(n):
        if i > 0 and dp[i] < 1:
            continue
        di = dp[i] * 10
        for k,v in d.items():
            t = di + v
            if dp[i+k] < t:
                dp[i+k] = t

    return dp[n]


print(main())

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
use=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0]=0
for i in range(N+1):
    for k in A:
        if i+use[k]<=N:
            dp[i+use[k]]=max(dp[i]+1,dp[i+use[k]])
ans=""
now=N
for i in range(dp[N]):
    for k in A:
        if now-use[k]>=0:
            if dp[now-use[k]]==dp[now]-1:
                ans+=str(k)
                now-=use[k]
                break
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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

recipe = [2, 5, 5, 4, 5, 6, 3, 7, 6]
available =[]
dp = [-1] * (N + 1)

for i in range(M):
	available.append((A[i], recipe[A[i] - 1]))
	
available.sort(reverse = True)
dp[0] = 0

for i in range(1, N + 1):
	for j in range(M):
		k = i - available[j][1]
		if k >= 0 and dp[k] >= 0:
			if dp[k] + 1 > dp[i]:
				dp[i] = dp[k] + 1

cost = 0
ans = ''

for i in range(dp[N]):
	for j in range(M):
		if N - cost - available[j][1] >= 0 and dp[N - cost - available[j][1]] == dp[N - cost] - 1:
			cost += available[j][1]
			ans += str(available[j][0])
			break
	
print(ans)

Solution (Python):




import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N,M = na()
A = na()
cost = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

d = {i:cost[i] for i in A}

dp = [-1]*(N+1)
dp[0] = 0
ans = [0]*(N+1)
for i in range(N+1):
    for j in range(10)[::-1]:
        if j not in d:
            continue
        elif d[j] > i:
            continue
        else:
            
            if dp[i] < dp[i-d[j]]+1:
                dp[i] = dp[i-d[j]]+1
                ans[i] = j
S = ""
pos = N

while pos!=0:
    
    S+=str(ans[pos])
    pos-=d[ans[pos]]


print(S)

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

blist=[False]*10
for a in alist:
  blist[a] = True

match=[6,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)

dp[0]=0
dp[1]=-1
for i in range(N+1):
  for j in range(1,10):
    if blist[j] and i+match[j]<=N:
      if dp[i+match[j]] < dp[i]+1:
        dp[i+match[j]] = dp[i]+1


answer_str = ""
while(N>0):
  for i in reversed(range(1,10)):
    if blist[i] and N-match[i] >= 0 and dp[N-match[i]] == dp[N]-1:
      answer_str += str(i)
      N -= match[i]
      break
      
print(answer_str)

Solution (Python):
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP=[-float("inf")]*(n+1)
DP[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP[i+1-D[A[j]]]!=float("inf") and DP[i+1-D[A[j]]]+1>=DP[i+1]:
      DP[i+1]=DP[i+1-D[A[j]]]+1
A.sort(reverse=True)
k=DP[n]
ans=""
cur=n
for _ in range(k):
  for j in range(m):
    if cur>=D[A[j]] and DP[cur-D[A[j]]]==DP[cur]-1:
      ans+=str(A[j])
      cur-=D[A[j]]
      break
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP=[-float("inf")]*(n+1)
DP[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP[i+1-D[A[j]]]!=float("inf") and DP[i+1-D[A[j]]]+1>=DP[i+1]:
      DP[i+1]=DP[i+1-D[A[j]]]+1
A.sort(reverse=True)
k=DP[n]
ans=""
cur=n
for _ in range(k):
  for j in range(m):
    if cur>=D[A[j]] and DP[cur-D[A[j]]]==DP[cur]-1:
      ans+=str(A[j])
      cur-=D[A[j]]
      break
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP=[-float("inf")]*(n+1)
DP[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP[i+1-D[A[j]]]!=float("inf") and DP[i+1-D[A[j]]]+1>=DP[i+1]:
      DP[i+1]=DP[i+1-D[A[j]]]+1
A.sort(reverse=True)
k=DP[n]
ans=""
cur=n
for _ in range(k):
  for j in range(m):
    if cur>=D[A[j]] and DP[cur-D[A[j]]]==DP[cur]-1:
      ans+=str(A[j])
      cur-=D[A[j]]
      break
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP=[-float("inf")]*(n+1)
DP[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP[i+1-D[A[j]]]!=float("inf") and DP[i+1-D[A[j]]]+1>=DP[i+1]:
      DP[i+1]=DP[i+1-D[A[j]]]+1
A.sort(reverse=True)
k=DP[n]
ans=""
cur=n
for _ in range(k):
  for j in range(m):
    if cur>=D[A[j]] and DP[cur-D[A[j]]]==DP[cur]-1:
      ans+=str(A[j])
      cur-=D[A[j]]
      break
print(ans)

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
l = min([m[a] for a in A])
dp = [0] * (N + 1)

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

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

dp = [-1]*(N+1)
dp[0] = ''
for a in A:
    if c[a] <= N:
        dp[c[a]] = str(a)

for i in range(N+1):
    for a in A:
        if i-c[a]>=0 and dp[i-c[a]]!=-1:
            if dp[i]==-1 or len(dp[i]) <= len(dp[i-c[a]])+1:
                dp[i] = str(a)+dp[i-c[a]]

ans = sorted(dp[N])
ans = ans[::-1]
ans = ''.join(ans)
print(ans)

Solution (Python):
INF = float('inf')
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 = [-INF]*(N+1)
dp[0] = 0
for a in A:
    if c[a] <= N:
        dp[c[a]] = 1

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

ans = ''
n = N
for a in A:
    if n-c[a]>=0:
        while dp[n] == dp[n-c[a]]+1:
            n -= c[a]
            ans = ans + str(a)
print(ans)

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n + 1)

dp[0] = 0
for i in range(1, n + 1):
    for j in a:
        if i < match[j - 1]:
            continue
        else:
            dp[i] = max(dp[i], dp[i - match[j - 1]] + 1)

num = []
k = n
for i in range(dp[n]):
    for j in a:
        if k >= match[j - 1]:
            if dp[k - match[j - 1]] == dp[k] - 1:
                num.append(j)
                k -= match[j - 1]
                break
print("".join(map(str, num)))

Solution (Python):
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

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

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and (dp[i-cost[j]]!=0 or i-cost[j]==0):
            p=max(p,int(dp[i-cost[j]]*10+j))
    dp[i]=p

print(dp[n])

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

maxnum = [-1] * (n+1)
cost = [0,2,5,5,4,5,6,3,7,6]
maxnum[0] = 0
for i in range(n+1):
    for num in a:
        if ( i+cost[num] < n+1 ):
            maxnum[i+cost[num]] = max(maxnum[i+cost[num]], num + maxnum[i]*10)

print(maxnum[n])

Solution (Python):
def larger(x, y):
	if x > y: return x
	else: return y

matchlist = [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 = [['', 0]]
for i in range(1, N+1):
	tmp = ''
	tmpmatch = 0
	for j in range(0, len(A)):
		if i-matchlist[A[j]] >= 0:
			if dp[i-matchlist[A[j]]][1]+matchlist[A[j]] == i:
				if len(tmp) < len(dp[i-matchlist[A[j]]][0])+1:
					tmp = larger(dp[i-matchlist[A[j]]][0]+str(A[j]), str(A[j])+dp[i-matchlist[A[j]]][0])
					tmpmatch = dp[i-matchlist[A[j]]][1]+matchlist[A[j]]
				elif len(tmp) == len(dp[i-matchlist[A[j]]][0])+1:
					if tmp != larger(tmp, larger(dp[i-matchlist[A[j]]][0]+str(A[j]), str(A[j])+dp[i-matchlist[A[j]]][0])):
						tmp = larger(dp[i-matchlist[A[j]]][0]+str(A[j]), str(A[j])+dp[i-matchlist[A[j]]][0])
						tmpmatch = dp[i-matchlist[A[j]]][1]+matchlist[A[j]]
	dp.append([tmp, tmpmatch])
print(dp[N][0])

Solution (Python):
n,m=map(int, input().split())
List=list(map(int, input().split()))
d=[0]*n*9+[-1]*n*9
for i in range(1, n+1):
    d[i]=max(d[i-int("0255456376"[a])]*10+a for a in List)
print(d[n])

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=list(map(int,input().split()))
ref=[0,2,5,5,4,5,6,3,7,6]
num=[0,0,0,0,0,0]
for i in a_list:
    if i>num[ref[i]-2]:
        num[ref[i]-2]=i
num_s=[]
for i in range(6):
    num_s.append([num[i],i])
num_s.sort(reverse=True)
temp=[0,0,0,0,0,0]
dp=[[0,0,0,0,0,0]]
for i in range(n):
    sub_list=[-1,-1,-1,-1,-1,-1]
    dp.append(sub_list)
for i in range(1,n+1):
    for j in range(6):
        if i-(j+2)>=0 and not num[j]==0:
            if dp[i-j-2][0]>=0:
                if sum(dp[i-j-2])+1>sum(dp[i]):
                    for k in range(6):
                        dp[i][k]=dp[i-j-2][k]
                    dp[i][j]=dp[i][j]+1
                elif sum(dp[i-j-2])+1==sum(dp[i]):
                    for h in range(6):
                        temp[h]=dp[i-j-2][h]
                    temp[j]=temp[j]+1
                    for k in num_s:
                        if temp[k[1]]>dp[i][k[1]]:
                            for h in range(6):
                                dp[i][h]=temp[h]
                            break
                        elif temp[k[1]]==dp[i][k[1]]:
                            pass
                        else:
                            break
                else:
                    pass
ans=''
for i in num_s:
    ans=ans+str(i[0])*dp[n][i[1]]
print(ans)

Solution (Python):
import copy
N, M = map(int, input().split())
A = sorted(map(int, input().split()))

digit2match_num = {i:j for i, j in zip(range(1, 10), [2,5,5,4,5,6,3,7,6])}

match_nums = sorted({digit2match_num[d]: d for d in A}.items())

rest = N


pattern_num = len(match_nums)
i = 0

ans = []

match_num, digit = match_nums[i]
n, rest = divmod(rest, match_num)
ans += [digit] * n

def make_tail(rest_match_num, ans):
  queue = [
    [[], rest_match_num]
  ]
  _ans = copy.copy(ans)
  flag = False
  tail = []
  for i in range(min(len(ans), 5)):
    new_queue = list()
    last_digit = ans.pop()
    last_match_num = digit2match_num[last_digit]
    for nums, rest_match_num in queue:
      rest_match_num += last_match_num
      new_queue.append([nums, rest_match_num])
      for match_num, digit in match_nums:
        if match_num <= rest_match_num:
          if rest_match_num == match_num:
            tail.append(
              sorted((ans + nums + [digit]), reverse=True)
            )
          elif match_num != last_match_num:
            new_queue.append([nums + [digit], rest_match_num - match_num])
        else:
          break
    queue = new_queue
  best = sorted(tail, key=lambda x: (len(x), x), reverse=True)[0]

  return best


if rest != 0:
  ans = make_tail(rest, ans)
print("".join(map(str, sorted(ans, reverse=True))))

Solution (Python):
l = [6, 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 + 10)
dp[0] = 0
for i in range(n):
    for num in a:
        dp[i + l[num]] = max(dp[i + l[num]], dp[i] * 10 + num)
print(dp[n])

Solution (Python):
def comp(a,b):
    if sum(a)<sum(b):
        return "right"
    elif sum(a)>sum(b):
        return "left"
    else:
        for i in range(8,-1,-1):
            if a[i]<b[i]:
                return "right"
            elif a[i]>b[i]:
                return "left"
        else:
            return "equal"

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])
    
maxlist=[[0]*9 for _ in range(N+1)]
 
for i in range(N+1):
    if i!=0 and sum(maxlist[i])==0:
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            ans=[maxlist[i][k] for k in range(9)]
            ans[b[0]-1]+=1
            _max=maxlist[i+b[1]]
            if comp(ans,_max) == "left":
                maxlist[i+b[1]]=[ans[k] for k in range(9)]
 
for i in range(8,-1,-1):
    print(str(i+1)*maxlist[N][i],end="")
print()

Solution (Python):
def comp(a,b):
    if sum(a)<sum(b):
        return "right"
    elif sum(a)>sum(b):
        return "left"
    else:
        for i in range(8,-1,-1):
            if a[i]<b[i]:
                return "right"
            elif a[i]>b[i]:
                return "left"
        else:
            return "equal"

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] in B and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])
    
maxlist=[[0]*9 for _ in range(N+1)]
 
for i in range(N+1):
    if i!=0 and sum(maxlist[i])==0:
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            
            ans=[maxlist[i][k] for k in range(9)]
            ans[b[0]-1]+=1
            _max=maxlist[i+b[1]]
            if comp(ans,_max) == "left":
                maxlist[i+b[1]]=[ans[k] for k in range(9)]
 
for i in range(8,-1,-1):
    print(str(i+1)*maxlist[N][i],end="")
print()

Solution (Python):
N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] in B and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+1)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]<_max[j]:
                        break
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
                        break
 
print(maxlist[N])

Solution (Python):
def chmax(a, b):
    if a == 'X':
        a = b
    elif len(a) < len(b):
        a = b
    elif len(a) == len(a):
        if a < b:
            a = b
    return a

match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = ['X' for _ in range(10010)]

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

dp[0] = ''

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

print(dp[N])

Solution (Python):
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    if x <= N:
        dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if t-x>=0:
            if dp[t-x]+1 == dp[t]:
                W[V[x]] += 1
                t -= x
                break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
dict = dict(zip([i for i in range(1, 10)], [2, 5, 5, 4, 5, 6, 3, 7, 6]))
INF = 10 ** (N // 2 + 1)
dp = [-INF for i in range(N + 21)]
for a in A:
    dp[dict[a]] = max(dp[dict[a]], a)
for i in range(N + 1):
    for j in range(1, 10):
        dp[i] = max(dp[i], dp[i - j] * 10 + dp[j], dp[j] * 10 + dp[i - j])
print(dp[N])

Solution (Python):
N, M = map(int,input().split())
L = list(map(int,input().split()))
K = [0,2,5,5,4,5,6,3,7,6]
A = sorted([[L[k],K[L[k]]] for k in range(M)])[::-1]
dp = [0 for k in range(N+1)]

for k in range(1,N+1):
    t = -float("inf")
    for j in range(M):
        if k-A[j][1]>=0:
            t = max(t, dp[k-A[j][1]]+1)
    dp[k] = t

ans = ""
keta = dp[N]
match = N
while keta > 0:
    for k in range(M):
        if match-A[k][1] >= 0:
            if dp[match-A[k][1]] == keta-1:
                ans += str(A[k][0])
                match -= A[k][1]
                keta -= 1
                break
print(ans)

Solution (Python):
import copy


def compare_num(ans_tmp, candidate):
    sum_tmp = sum(ans_tmp)
    sum_candidate = sum(candidate)
    if sum_tmp == sum_candidate:
        for t, c in zip(ans_tmp, candidate):
            if t > c:
                return ans_tmp
            elif t < c:
                return candidate
        else:
            return ans_tmp

    else:
        return ans_tmp if sum_tmp > sum_candidate else candidate


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

match_num_array = [2, 5, 5, 4, 5, 6, 3, 7, 6]
can_use_num_tmp = [-1, -1, -1, -1, -1, -1]
for A in A_array:
    can_use_num_tmp[match_num_array[A - 1] - 2] = max(
        A, can_use_num_tmp[match_num_array[A - 1] - 2])
can_use_num_tmp.sort()

can_use_num = []
can_use_num_match = []

for tmp in can_use_num_tmp[::-1]:
    if tmp == -1:
        break
    can_use_num.append(tmp)
    can_use_num_match.append(match_num_array[tmp - 1])


ans = []

ans.append([0] * len(can_use_num))

for n in range(1, N + 1):
    ans_tmp = -1

    for i, match_num in enumerate(can_use_num_match):
        if n - match_num >= 0 and ans[n - match_num] != -1:
            candidate = copy.deepcopy(ans[n - match_num])
            candidate[i] += 1
            ans_tmp = candidate if ans_tmp == -1 else compare_num(
                ans_tmp, candidate)
    ans.append(ans_tmp)

ans_str = ""
for ans_num, ans_count in zip(can_use_num, ans[N]):
    ans_str += (str(ans_num) * ans_count)

print(ans_str)

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for _ in range(n + 1)]
INF = 10 ** 9
for i in range(1, n + 1):
    c = [dp[i - b[aj]] for aj in a if i >= b[aj]]
    if len(c) > 0:
        dp[i] = max(c) + 1
    else:
        dp[i] = -INF

x = n
i = 0
ans = ''
while(True):
    for aj in a:
        if x - b[aj] >= 0 and dp[x - b[aj]] == dp[n] - i - 1:
            i += 1
            x -= b[aj]
            ans += str(aj)
            break
    if i == dp[n]:
        break
print(ans)

Solution (Python):





from functools import lru_cache
import sys

sys.setrecursionlimit(100000000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]



@lru_cache(maxsize=1000000)
def f(n):
    maxval = -float('inf')
    for a in A:
        tmp = n - match[a]
        if tmp == 0:
            maxval = max(maxval, a)
        elif tmp > 0:
            
            maxval = max(maxval, f(n - match[a]) * 10 + a)
    return maxval

@lru_cache(maxsize=1000000)
def f2(n):
    if n < 0:
        return 0
    n = list(str(n))
    n.sort(reverse=True)
    return int("".join(n))

ans = f(N)
print(f2(ans))

Solution (Python):



import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    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(N+1):
        for a in A:
            if i < MATCH_NUM[a]:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    res = ''
    for _ in range(max_digit_num):
        m = -1
        for a in A:
            if N < MATCH_NUM[a]:
                continue
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if a > m:
                    m = a
        res += str(m)
        N -= MATCH_NUM[m]
    print(res)
main()

Solution (Python):
import sys
from operator import itemgetter
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [i for i in range(1, 10)]
C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
inf = float('inf')
costs = {m: C[m-1] for m in A}
dp = deque([0])

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

digits = list(costs.keys())
digits.sort(reverse=True)
result = deque()
num = N
for _ in range(dp[N]):
        for i in digits:
                if num >= costs[i] and dp[num-costs[i]] != -inf and dp[num-costs[i]] == dp[num]-1:
                        result.append(str(i))
                        num -= costs[i]
                        break

print(''.join(result))

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

cost = sorted(list(zip([[2, 5, 5, 4, 5, 6, 3, 7, 6][a-1] for a in A], A)), key=lambda x: (x[0], -x[1]))





tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key=lambda x:-x[1])



dp = [0] + [-10] * (N)
for i in range(2, N+1):
    dp[i] = max([-10] + [dp[i-c]+1 for c, _ in cost if i >= c])

n = N
out = ""
i = 0
while n:
    c, a = cost[i]
    if (n >= c) and (dp[n-c] == dp[n] - 1):
        n -= c
        out += str(a)
    else:
        i += 1
print(out)

Solution (Python):
import itertools

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

len_set = set(L[x] for x in A)

INF = 10**18
can_make = [-INF]*(N+1)
can_make[0] = 0 

for n in range(1,N+1):
  for x in len_set:
    if n-x >= 0 and can_make[n] < can_make[n-x] + 1:
        can_make[n] = can_make[n-x] + 1

answer = []

A.sort(reverse = True)

for a in A:
  x = L[a]
  while N-x >= 0 and can_make[N] == can_make[N-x]+1:
    answer.append(str(a))
    N -= x
      
answer = ''.join(answer)
print(answer)

Solution (Python):
def sub(N, M, As):

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    NINF = -10**6
    dp_table = [NINF for _ in range(N+1)]
    dp_table[0] = 0
    for i in range(N):
        if dp_table[i] < 0:
            continue
        for a in As:
            cost = i + d_cost[a]
            if cost <= N:
                dp_table[cost] = max(dp_table[cost], dp_table[i] + 1)

    Lmax = dp_table[N]

    life = N
    buf = []
    for i in range(Lmax):
        oks = []
        for a in As:
            if life - d_cost[a] < 0:
                continue
            if dp_table[life - d_cost[a]] == dp_table[life] - 1:
                oks.append(a)
        
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))
            

if __name__ == "__main__":
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]
    sub(N, M, As)

Solution (Python):
n, m = list(map(int, input().split()))
s = {e for e in list(map(int, input().split()))}
d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dp = [-1 for i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
  for e in s:
    if i-d[e]>=0 and dp[i-d[e]]>=0:
      dp[i] = max(dp[i], dp[i-d[e]]+1)

ans = ""
j = n
for i in range(dp[n]):
  for e in sorted(s, reverse=True):
    if j-d[e]>=0 and dp[j]-1==dp[j-d[e]]:
      ans += str(e)
      j -= d[e]
      break
print(ans)

Solution (Python):
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
cost = [0,2,5,5,4,5,6,3,7,6] 
dp = [-1]*(n+1)
dp[0] = 0

for i in range(2,n+1):
    for j in range(0,m):
        if i-cost[a[j]] <0:
            continue
        if dp[i-cost[a[j]]] == -1:
            continue
        else:
            dp[i] = max(dp[i],dp[i-cost[a[j]]]+1)

ans = list()
read = n
a.sort()
a.reverse()

while read > 0:
    for i in range(0,m):
        if read < cost[a[i]]:
            continue
        if dp[read-cost[a[i]]] == dp[read]-1:
            ans.append(str(a[i]))
            read -= cost[a[i]]
            break
    
print("".join(ans))

Solution (Python):
N, M = map(int, input().split())
A = tuple([int(s) for s in input().split()])
m = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)
dp = [None for _ in range(N+1)]
dp[0] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for n in range(2, N+1):
    for a in A:
        dn = m[a]
        if n - dn < 0 or dp[n - dn] is None:
            continue
        state = dp[n - dn][:]
        state[0] += 1
        state[10 - a] += 1
        if dp[n] is None:
            dp[n] = state
        else:
            dp[n] = max(dp[n], state)
for i in range(1, 10):
    print(str(10-i) * dp[N][i], end="")
print("")

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

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

for i in range(N):
    tmp = []
    for A in Alist:
        if (i+1 - dic[A-1]) < 0:
            tmp.append(-1)
        else:
            if dp[i+1 - dic[A-1]] != -1:
                tmp.append(dp[i+1 - dic[A-1]] + 1)
            else:
                tmp.append(-1)
        dp[i+1] = max(tmp)


output = []
output_dic = []
for i in range(dp[N]):
    for A in Alist[::-1]:
        if N - sum(output_dic) - dic[A-1] >= 0:
            if dp[N - sum(output_dic) - dic[A-1]] == (dp[N - sum(output_dic)] - 1):
                output.append(A)
                output_dic.append(dic[A-1])
                break

out = ''
for i in range(len(output)):
    out += str(output[i])

print(out)

Solution (Python):
import collections
N, M = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
n_m = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
m_n = {}
for a in A:
    m_n[n_m[a]] = a
dp = collections.defaultdict(lambda: -float('inf'))
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = max(dp[i - m] + 1 for m, n in m_n.items())
ans = ''
ms = sorted(m_n.keys(), key=lambda _: m_n[_], reverse=True)
d = dp[N]
while N:
    for m in ms:
        if dp[N - m] == dp[N] - 1:
            N -= m
            ans += str(m_n[m])
            break
print(ans)

Solution (Python):
if __name__ == "__main__":
  l = [0,2,5,5,4,5,6,3,7,6]
  n,m = list(map(int,input().split()))
  a = list(map(int,input().split()))
  res = ''
  INF = 10**4
  
  dp = [[0,0] for i in range(n+1)]
  for i in range(n):
    for j in range(m):
      if dp[i][1] + l[a[j]] != i + l[a[j]] or i + l[a[j]] > n:
        pass
      else:
        dp[i + l[a[j]]][0] = max(dp[i][0] + 1, dp[i + l[a[j]]][0])
        dp[i + l[a[j]]][1] = dp[i][1] + l[a[j]]
  for i in range(1,n): dp[i][0] = -INF if dp[i][0] == 0 else dp[i][0]
  
  a.sort(reverse = True)
  i = n
  while i > 0:
    for j in range(m):
      if i >= l[a[j]] and dp[i - l[a[j]]][0] + 1 == dp[i][0]:
        res += str(a[j])
        i -= l[a[j]]
        break
      else:
        pass
  print(res)