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 = [int(i) for i in input().split()]

l = [0,2,5,5,4,5,6,3,7,6]
inf = float("INF")
dp = [-inf] * (n+10)
d = [-inf] * (n+10)
dp[0] = 0
d[0] = 0
for i in range(n):
  if dp[i] == -inf: continue
  tmp = dp[i]
  k = d[i]
  for ai in a:
    dp[l[ai] + i] = max(dp[l[ai] + i], dp[i] + k * ai, dp[i] * 10 + ai)
    d[i + l[ai]] = max(d[i + l[ai]], k + 1)
print(dp[n])

Solution (Python):
n, m = (int(x) for x in input().split())
A = sorted([int(x) for x in input().split()])[::-1]
cost = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)
dp = [[-1] * (n+1) for _ in range(m+1)]
for i in range(m+1):
  dp[i][0] = 0
for i in range(m):
  for j in range(1, n+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j >= cost[A[i]]:
      if dp[i+1][j-cost[A[i]]] == -1:
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
      else:
        dp[i+1][j] = max(dp[i+1][j], 10 * dp[i+1][j-cost[A[i]]] + A[i])
print(dp[m][n])

Solution (Python):
n, m = (int(x) for x in input().split())
A = sorted([int(x) for x in input().split()])[::-1]
cost = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(m):
  for j in range(1, n+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j >= cost[A[i]]:
      if dp[i+1][j-cost[A[i]]] == 0:
        if j == cost[A[i]]:
          dp[i+1][j] = max(A[i], dp[i][j])
        else:
          dp[i+1][j] = max(dp[i+1][j], dp[i][j])
      else:
        dp[i+1][j] = max(dp[i+1][j], 10 * dp[i+1][j-cost[A[i]]] + A[i])
print(dp[m][n])

Solution (Python):
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cost=[0,2,5,5,4,5,6,3,7,6]
    dp=[-n-n]*(n+1)
    dp[0]=0
    ans=[]
    for i in range(1,n+1):
        for j in a:
            if i>=cost[j]:
                dp[i]=max(dp[i],dp[i-cost[j]]+1)
    cnt=n
    while cnt:
        for j in a:
            if cnt>=cost[j] and dp[cnt-cost[j]]==dp[cnt]-1:
                ans.append(j)
                cnt-=cost[j]
                break
    for j in ans:
        print(j, end="")
    print("")

if __name__ == '__main__':
    main()

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

A.sort()
A.reverse()

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

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

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

max_list = []
while N:
  for j in A:
    if N >= match[j] and dp[N] == dp[N - match[j]] + 1:
      max_list.append(j)
      N -= match[j]
      break

for j in max_list:
  print(j, end="")
print("")

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

A.sort()
A.reverse()

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

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

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

max_list = []
while N:
  for j in A:
    if N >= match[j] and dp[N] == dp[N - match[j]] + 1:
      max_list.append(j)
      N -= match[j]
      break

for j in max_list:
  print(j, end="")
print("")

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
numk={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+numk[j]<=N:
            dp[i+numk[j]]=max(dp[i+numk[j]],dp[i]+1)
m=N
ans=[]
while m>0:
    for i in A:
        if m-numk[i]>=0 and dp[m-numk[i]]+1==dp[m]:
            ans.append(str(i))
            m-=numk[i]
            break
print(''.join(ans))

Solution (Python):
n,m=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
x=[0,2,5,5,4,5,6,3,7,6]
d=dict()
for j in l:
    d[x[j]]=j
INF=float('inf')
dp=[-INF for i in range(n+1)]
dp[0]=0
l=d.keys()
for i in range(2,n+1):
    for j in d.keys():
        if j<=i:
            dp[i]=max(dp[i],dp[i-j]*10+d[j])
print(dp[n])

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
numk={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+numk[j]<=N:
            dp[i+numk[j]]=max(dp[i+numk[j]],dp[i]+1)
m=N
ans=[]
while m>0:
    for i in A:
        if m-numk[i]>=0 and dp[m-numk[i]]==dp[m]-1:
          ans.append(str(i))
          m-=numk[i]
          break
print(''.join(ans))

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
numk={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+numk[j]<=N:
            dp[i+numk[j]]=max(dp[i+numk[j]],dp[i]+1)
m=N
ans=[]
while m>0:
    for i in A:
        if m-numk[i]>=0 and dp[m-numk[i]]==dp[m]-1:
          m-=numk[i]
          ans.append(str(i))
          break
print("".join(ans))

Solution (Python):
N,M=map(int,input().split())
num={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
A=list(map(int,input().split()))
A.sort(reverse = True)
dp = [0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+num[j]<=N:
            dp[i+num[j]] = max(dp[i+num[j]],dp[i]+1)
ans = []
m=N
while m>0:
    for i in A:
        if m-num[i]>=0 and dp[m-num[i]]==dp[m]-1:
          m-=num[i]
          ans.append(str(i))
          break
print("".join(ans))

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

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

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

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

dp = ["0"] * 10010

dp[0] = ""

def greater(x, y):
    if len(x) == len(y):
        return max(x, y)
    else:
        return x if len(x) > len(y) else y

for i in range(N):
    if dp[i] != "0":
        for num in A:
            dp[i+match_dict[num]] = greater(dp[i+match_dict[num]], dp[i]+str(num))

print(dp[N])

Solution (Python):
n,m=map(int,input().split())
A=reversed(sorted(map(int,input().split())))
M=[2,5,5,4,5,6,3,7,6]
D={}
E={}
for a in A:
    if M[a-1] in D:
        continue
    else:
        D[M[a-1]]=a
        E[a]=M[a-1]
S=list(reversed(sorted(E)))
        
dp=[0]*(n+2)
for i in range(1,n+2):
    cnt=-1
    for d in D:
        if i-d>=0:
            if dp[i-d]!=-1:
                cnt=max(dp[i-d]+1,cnt)
    dp[i]=cnt    
k=dp[n]
ans=""

while k>0:
    for s in S:
        x=E[s]
        if n-x<0:
            continue
        if dp[n-x]==k-1:
            ans+=str(s)
            k-=1
            n-=x
            break
print(ans)

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

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

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

for i in range(n):
  for j in A:
    if i + li[j - 1] <= n:
      dp[i + li[j - 1]] = max(dp[i + li[j - 1]], dp[i] * 10 + j)
print(dp[-1])

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

match_dict = {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()))

def greater(a, b):
    if len(a) == len(b):
        return max(a, b)
    elif len(a) > len(b):
        return a
    else:
        return b        

dp = ["0"] * 11000

dp[0] = "" 

for i in range(N+1):
    
    for a in A:
        if i - match_dict[a] >= 0 and dp[i-match_dict[a]] != '0':
            dp[i] = greater(dp[i - match_dict[a]] + str(a), dp[i])

print(dp[N])

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

match_dict = {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] * (N+1)
dp[0] = 0

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

ans = ''
A.sort(reverse=True)

i = N
while i:
    for a in A:
        if i - match_dict[a] >= 0 and dp[i - match_dict[a]] == dp[i] - 1:
            ans += str(a)
            i -= match_dict[a]
            break

print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    lst = list(map(int, input().split()))
    mapk = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
    
    dp = [0 for _ in range(N+1)] 
    for i in range(1, N+1):
        tmp = []
        for k in lst:
            if (i-mapk[k])>=0:
                tmp.append(dp[i-mapk[k]] + 1)
            else:
                tmp.append(-float('inf'))
        dp[i] = max(tmp)
    
    
    ans = ''
    X = N
    lst = sorted(lst, reverse=True)
    for _ in range(dp[N]):
        for k in lst:
            if (X-mapk[k]>=0) and (dp[X - mapk[k]] == dp[X] - 1):
                ans += str(k)
                X -= mapk[k]
                break
    print(ans)
main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = sorted(inpl(), reverse = True)
b = [0,2,5,5,4,5,6,3,7,6]
dp = [0] * (n+1)

for i in a:
    w,v = b[i],i
    for j in range(n+1):
        if j < w:
            continue
        if j%w == 0 or dp[j-w]:
            dp[j] = max(dp[j], dp[j-w]*10 + v)
    
print(dp[-1])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    
    b = set()
    matti = [2,5,5,4,5,6,3,7,6]
    for i in a:
        b.add(matti[i-1])

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

    keta = dp[-1]
    res = []
    a.sort(reverse=True)
    cnt = n
    while cnt>0:
        for i in a:
            if cnt >= matti[i-1]:
                if dp[cnt]-dp[cnt-matti[i-1]]==1:
                    res.append(str(i))
                    cnt -= matti[i-1]
                    break
    print(''.join(res))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 4)
from fractions import gcd

num = [10**9, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    dp = [[""]*(n+1) for _ in range(len(a))]
    dp[0][num[a[0]]] = str(a[0])
    for i in range(num[a[0]], n+1):
        if len(dp[0][i-num[a[0]]]) > 0:
            dp[0][i] = dp[0][i-num[a[0]]] + str(a[0])
    for i in range(1, len(a)):
        for j in range(n+1):
            if j < num[a[i]]:
                dp[i][j] = dp[i-1][j]
            else:
                if j == num[a[i]] or dp[i][j-num[a[i]]] != "":
                    buf = dp[i][j-num[a[i]]] + str(a[i])
                    if len(buf) < len(dp[i-1][j]):
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = buf
                else:
                    dp[i][j] = dp[i-1][j]
    ans = list(dp[len(a)-1][n])
    ans.sort(reverse=True)
    print("".join(ans))

if __name__ == "__main__":
    main()

Solution (Python):
N,_ = map(int, input().split())
A = [int(i) for i in input().split()]

INF = "-"

def chmax(a:str,b:str):
    if a == INF: return b
    elif len(a) < len(b): return b
    elif len(a) == len(a):
        if a < b: return b
    return a


cnt = dict(zip(range(1,10), [2,5,5,4,5,6,3,7,6]))


dp = [INF] * (10 ** 5)


dp[0] = ""


for i in range(N):
    if dp[i] == INF: continue
    for a in A:
        dp[i + cnt[a]] = chmax(dp[i + cnt[a]], dp[i] + chr(ord("0") + a))

print(dp[N])

Solution (Python):
n,m=map(int,input().split())
sz=[0,2,5,5,4,5,6,3,7,6]
l=[]
dp=[0]*(n+1)
l=list(map(int,input().split()))
l.sort(reverse=True)
dp[0]=1
for i in range(1,n+1):
    for j in l:
        if i-sz[j]>=0 and dp[i-sz[j]]>0:
            dp[i]=max(dp[i],1+dp[i-sz[j]])

ans=[]

cur=n
while cur>0:
 
    for j in l:
        if cur-sz[j]>=0:
            if dp[cur]==1+dp[cur-sz[j]] and dp[cur-sz[j]]>0:
                ans.append(j)
                cur-=sz[j]
                break
ans.sort(reverse=True)
print(''.join(map(str,ans)))

Solution (Python):
n,m = map(int,input().split())
num = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a = list(map(int,input().split()))
a.sort(reverse = True)
dp = [0]+[-1]*(n+1)
for i in range(n):
    for j in a:
        if i+num[j] <=n:
            dp[i+num[j]] = max(dp[i+num[j]],dp[i]+1)
ans = []
match = n
while match > 0:
    for i in a:
        if match-num[i] >= 0 and dp[match-num[i]] == dp[match]-1:
            match -= num[i]
            ans.append(str(i))
            break
print("".join(ans))

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

dp = [(-1, -1)]*(n+1)
dp[0] = (0, -1)
for k in range(1, n+1):
    max_value = -1
    max_d = -1
    for num in A:
        if k >= digit[num]:
            suf, d = dp[k - digit[num]]
            if suf >= 0:
                value = num * (10 ** (d + 1)) + suf
                if value > max_value:
                    max_value = value
                    max_d = d + 1

    dp[k] = (max_value, max_d)
print(dp[n][0])

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]
wv=[]
for i in a:
  wv.append((b[i],i))
wv.sort()
dp=[-1 for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
  for w,v in wv:
    if i-w<0:
      continue
    if dp[i-w]==-1:
      continue
    dp[i]=max(dp[i],dp[i-w]*10+v)
print(dp[n])

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

Solution (Python):
def main():
    N, M = map(int, input().split())
    A = set(map(int, input().split()))


    cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    B = []
    for i in range(1, 10):
        if i in A:
            B.append((cost[i], i))

    B = B[::-1]
    dp = [[-1, -1] for i in range(N+1)]
    dp[0][0] = 0
    for i in range(1, N+1):
        for x, y in B:
            if i >= x and dp[i-x][0] >= 0:
                if dp[i][0] < dp[i-x][0] + 1:
                    dp[i][0] = dp[i-x][0] + 1
                    dp[i][1] = y
    id = N
    ans = []
    
    while(id > 0):
        ans.append(dp[id][1])
        id -= cost[dp[id][1]]
    ans.sort(reverse=True)
    print("".join(map(str, ans)))
main()

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

match = [10**18, 2, 5, 5, 4, 5, 6, 3, 7, 6]


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

for i in range(N):
    for a in A:
        m = match[a]
        if i + m <= N and dp[i + m] < dp[i] + 1:
            dp[i + m] = dp[i] + 1

ans = []
while N > 0:
    for a in A:
        m = match[a]
        if N - m >= 0 and dp[N - m] + 1 == dp[N]:
            ans.append(a)
            N -= m
            break

ans.sort(reverse=True)

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

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

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

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    W,n = LI()
    a = LI()
    for i in range(n):
        a[i] -= 1
    a.sort(reverse = True)
    b = [2,5,5,4,5,6,3,7,6]
    dp = [-float("inf")]*(W+1)
    dp[0] = 0
    for i in range(n):
        v = a[i]+1
        w = b[a[i]]
        for j in range(W):
            nj = j+w
            if nj > W:
                continue
            nd = dp[j]*10+v
            if dp[nj] < nd:
                dp[nj] = nd
    print(dp[W])
    return


if __name__ == "__main__":
    solve()

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

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
count = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for _ in range(N+1)]
for i in range(N+1):
    if i > 0 and all(dp[i][j] == 0 for j in range(10)):
        continue
    for a in A:
        if i + count[a] <= N:
            ndp = list(dp[i])
            ndp[a] += 1
            ca = sum(ndp)
            cb = sum(dp[i+count[a]])
            if ca > cb:
                dp[i+count[a]] = ndp
            if ca == cb:
                for j in range(10)[::-1]:
                    if dp[i+count[a]][j] > ndp[j]:
                        break
                    if dp[i+count[a]][j] < ndp[j]:
                        dp[i+count[a]] = ndp
                        break
ans = ''
for i in range(10)[::-1]:
    ans += str(i) * dp[N][i]
print(ans)

Solution (Python):
n,m = map(int,input().split())
A = list(map(int,input().split()))
L = [2,5,5,4,5,6,3,7,6]
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    for j in range(m):
        if i-L[A[j]-1] < 0:
            None
        else:
            dp[i] = max(dp[i-L[A[j]-1]]+1, dp[i])
A.sort()
A.reverse()
cur = n
ans = ''
while cur != 0:
    for i in range(m):
        temp = A[i]
        if cur-L[temp-1] >= 0:
            if dp[cur-L[temp-1]] == dp[cur]-1:
                ans = ans+str(temp)
                cur -= L[temp-1]
                break
print(ans)

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


COST = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
A = sorted(A, reverse=True)

best = [None for _ in range(N + 1)]
best[0] = tuple([0] * len(A))
for n in range(N + 1):
    for ai, a in enumerate(A):
        before = n - COST[a]
        if before < 0 or best[before] is None:
            continue
        val = tuple(x + (1 if i == ai else 0) for i, x in enumerate(best[before]))
        if (
            best[n] is None
            or sum(best[n]) < sum(val)
            or (sum(best[n]) == sum(val) and best[n] < val)
        ):
            best[n] = val
print(''.join(sorted(''.join(str(d) * n for d, n in zip(A, best[N])), reverse=True)))

Solution (Python):
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

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

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

print(dp[-1][0])

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]
li=[-100]*(N+1)
li[0]=0
for i in range(N+1):
  for a in A:
    if weight[a]+i<=N:
      li[weight[a]+i]=max(li[weight[a]+i],a+10*li[i])
print(li[N])

Solution (Python):
n,m=map(int,input().split())
A=[2,5,5,4,5,6,3,7,6]
B=list(map(int,input().split()))
B=sorted(B,reverse=True)
C=[]
for i in range(m):
  C.append(A[B[i]-1])
C=set(C)
C=sorted(list(C))
dp=[-10**10]*(n+10)
dp[0]=0
for i in range(1,n+1):
  for j in range(len(C)):
    if dp[i]<dp[i-C[j]]+1:
      dp[i]=dp[i-C[j]]+1
S=[]
for i in range(dp[n]):
  for j in range(len(B)):
    if dp[n-A[B[j]-1]]==dp[n]-1:
      n=n-A[B[j]-1]
      S.append(B[j])
      break
for i in range(len(S)):
  print(S[i],end="")
print()

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
dp = [-1]*(n+9)
dp[0] = 0
for i in range(n):
    if dp[i]>=0:
        for x in a:
            c = cs[x]
            dp[i+c] = max(dp[i+c], dp[i]+1)
ans = []
t = n
k = dp[n]
for j in range(k,0,-1):
    for i in range(m-1,-1,-1):
        x = a[i]
        c = cs[x]
        if t>=c and dp[t-c]==j-1:
            ans.append(str(x))
            t -= c
            break
print(''.join(ans))

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 5

def foo(n,dep):
    if dep>DEPMAX or n<0:
        ret = "-1"
    elif n==0:
        ret = ""
    elif n%mn==0:
        ret = str(mni)*(n//mn)
    else:
        mxs = "-1"
        for x in a:
            v = foo(n-cs[x],dep+1)
            if v=="-1":
                continue
            vv = v+str(x)
            if int(vv)>int(mxs):
                mxs = vv
            vv = str(x)+v
            if int(vv)>int(mxs):
                mxs = vv
        ret = mxs
    
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break




print(foo(n,0))

Solution (Python):





from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys


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

data=[]
for i,a in enumerate([2,5,5,4,5,6,3,7,6]):
    if i+1 in A:
        data.append([a,i+1])

dic={}
for a,i in reversed(data):
    dic[i]=0
dp=[copy.copy(dic) for i in range(N+1)]

def main(dic1,dic2):
    dic1=sorted([[str(i),dic1[i]] for i in dic],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic2[i]] for i in dic],key=lambda x:x[0],reverse=True)
    for a,b in zip(dic1,dic2):
        if a[1]>b[1]:
            return(0)
        if a[1]<b[1]:
            return(1)
    return(0)

def _sum(dic):
    count=0
    for i in dic:
        count+=dic[i]
    return(count)


for a,n in data:
    tempdic=copy.copy(dic)
    tempdic[n]+=1
    if len(dp)-1>=a:
        flag=main(dp[a],tempdic)
        if flag:
            dp[a]=tempdic
    for i in range(len(dp)):
        if i>=a and _sum(dp[i-a]):
            if _sum(dp[i])<_sum(dp[i-a])+1:

                tempdic=copy.copy(dp[i-a])
                tempdic[n]+=1
                dp[i]=tempdic
            elif _sum(dp[i])==_sum(dp[i-a])+1:
                dp[i-a][n]+=1
                flag=main(dp[i],dp[i-a])
                dp[i-a][n]-=1
                if flag:
                    tempdic=copy.copy(dp[i-a])
                    tempdic[n]+=1
                    dp[i]=tempdic
dic=dp[N]
a=""
dic=sorted([[str(i),dic[i]] for i in dic],key=lambda x:x[0],reverse=True)
for i,z in dic:
    for m in range(z):
        a+=i
print(a)

Solution (Python):
from collections import defaultdict
n,m=map(int,input().split())
A=list(map(int,input().split()))
hon2=[1]
hon5=[2,3,5]
hon4=[4]
hon3=[7]
hon6=[6,9]
hon7=[8]
usenum=[]
usematch=defaultdict(int)
for a in A:
    if a in hon2:
        usenum.append(2)
        usematch[2]=max(a, usematch[2])
    if a in hon5:
        usenum.append(5)
        usematch[5]=max(a, usematch[5])
    if a in hon4:
        usenum.append(4)
        usematch[4]=max(a, usematch[4])
    if a in hon3:
        usenum.append(3)
        usematch[3]=max(a, usematch[3])
    if a in hon6:
        usenum.append(6)
        usematch[6]=max(a, usematch[6])
    if a in hon7:
        usenum.append(7)
        usematch[7]=max(a, usematch[7])
usenum=list(set(usenum))
usenum.sort()
dp=[-1]*(n+11)
dp[0]=0
for i in range(n+1):
    if dp[i]==-1:
        continue
    for num in usenum:
        dp[i+num]=max(10*dp[i]+usematch[num], dp[i+num])
print(dp[n])

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

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

N=[0,2,5,5,4,5,6,3,7,6]
X=[]
dp=[0]+[-1]*n*9

for i in range(n):
    for j in A:
        if dp[i]>=0:
            dp[i+N[j]]=max(dp[i+N[j]],dp[i]*10+j)

print(dp[n])

Solution (Python):
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
lis = [2,5,5,4,5,6,3,7,6]
def new_val(num1,num2): 
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2
    ret = (10**len(str(num2)))*num1 + num2
    return ret

dp = [[-(10**10) for i in range(1+n)] for j in range(1+m)]
for i in range(m):
    dp[i][0]=0

for i in range(m):
    num=a[i]
    honsu=lis[a[i]-1]
    for j in range(1+n):
        if j<honsu:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(new_val(dp[i+1][j-honsu] , num),dp[i][j])
print(dp[-1][-1])

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

A.sort(reverse=True)

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

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

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

ans = ''

i = N
for k in range(dp[N]):
    for a in A:
        if i - cost[a] >= 0 and dp[i - cost[a]] != -1 and dp[i - cost[a]] == dp[i] - 1:
            ans += str(a)
            i -= cost[a]
            break

print(ans)

Solution (Python):
match = {
    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()



inf = 10**18
dp = [-1] * (N + 10)
dp[0] = 0
for i in range(N):
    if dp[i] == -1:
        continue
    for a in A:
        dp[i + match[a]] = max(dp[i + match[a]], dp[i] + 1)

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

print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = ["-"]*(N+10)
    dp[0] = ""
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(N+1):
        if dp[i] == "-":
            continue
        for a in A:
            cur = dp[i+match[a]]
            ne = dp[i] + str(a)
            if len(cur) < len(ne) or cur < ne:
                dp[i+match[a]] = ne
    
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = ["-"]*(N+10)
    dp[0] = ""
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(N+1):
        if dp[i] == "-":
            continue
        for a in A:
            cur = dp[i+match[a]]
            ne = dp[i] + str(a)
            if len(cur) < len(ne) or cur < ne:
                dp[i+match[a]] = ne
    
    print(dp[N])


if __name__ == '__main__':
    main()

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

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    use = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    U = dict()
    for a in A:
        if use[a] in U: U[use[a]] = max(a, U[use[a]])
        else: U[use[a]] = a

    DP = [-1] * (N + 1)
    DP[0] = 0
    for i in range(N):
        if DP[i] > -1:
            for key in U:
                if i + key <= N:
                    DP[i + key] = max(DP[i + key], DP[i] * 10 + U[key])
    print(DP[N])

    return 0

if __name__ =="__main__":
    solve()

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])
'''
dp[i]をちょうどi本使った時に表せる最大の数と考えれば
(aが数字の値で降順ソートされていることにも注意して)、
a[i][0]をi番目に大きい数字、a[i][1]をその数を表すのに
必要なマッチ棒の本数として、
dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
という更新を行ってdp[n]を求めれば良いです。
また、ある数字の組が決まればマッチの本数が一意に定まり
一番上の桁から順に大きい数字を入れるのが最適なので、
aを降順ソートして大きい数字から順に取ってDPを行うことで
これを実現することができます。
e.g. 9→3→3→2の順番に取れば、
((((0×10+9)×10+3)×10+3)×10+2)=9332((((0×10+9)×10+3)×10+3)×10+2)=9332
'''

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
table = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
inf = (-1) * 10**5

dp = [inf for i in range(N+1)]
dp[0] = 0
for i in range(N+1):
    for j in range(len(A)):
        if i + table[A[j]] > N:
            continue
        if dp[i + table[A[j]]] < dp[i] + 1:
            dp[i + table[A[j]]] = dp[i] + 1


ans = ""
cur_cost = N

for _ in range(dp[N]):
    
    for j in range(len(A)):
        if cur_cost - table[A[j]] < 0:
            continue
        if dp[cur_cost - table[A[j]]] == dp[cur_cost] - 1:
            ans += str(A[j])
            cur_cost -= table[A[j]]
            break
print(ans)

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

match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
d = dict()
for e in a:
    d[e] = match[e]

dp = [-1] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    for k, v in d.items():
        if i - v >= 0 and dp[i-v] != -1:
            dp[i] = max(dp[i], dp[i-v] * 10 + k)

print(dp[n])