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 sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    for a in A:
        if a==3:
            try:
                A.remove(2)
            except:
                pass
        elif a==5:
            try:
                A.remove(2)
            except:
                pass
            try:
                A.remove(3)
            except:
                pass
        elif a==9:
            try:
                A.remove(6)
            except:
                pass
    d={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
    l=[d[x] for x in A]
    dp=[[0]*(N+1) for _ in range(len(l)+1)]
    prev_w=[[0]*(N+1) for _ in range(len(l)+1)]
    real_w=[[0]*(N+1) for _ in range(len(l)+1)]
    for num in range(len(l)):
        for w in range(N+1):
            if w>=l[num]:
                if dp[num+1][w]<dp[num+1][w-l[num]]+1 and real_w[num+1][w-l[num]]+l[num]==w:
                    dp[num+1][w]=dp[num+1][w-l[num]]+1
                    prev_w[num+1][w]=w-l[num]
                    real_w[num+1][w]=w
            if dp[num+1][w]<dp[num][w]:
                dp[num+1][w]=dp[num][w]
                prev_w[num+1][w]=w
                real_w[num+1][w]=w
    l2=[]
    cur_w=N
    for num in range(len(l)-1,-1,-1):
        while True:
            if prev_w[num+1][cur_w]==cur_w-l[num]:
                l2.append(str(A[num]))
                cur_w=prev_w[num+1][cur_w]
            else:
                cur_w=prev_w[num+1][cur_w]
                break
    print(''.join(l2))

if __name__ == '__main__':
    main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    A=sorted(LI(), reverse=True)
    num_cost = {
        1:2,
        2:5,
        3:5,
        4:4,
        5:5,
        6:6,
        7:3,
        8:7,
        9:6
    }


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

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

    ans = []
    while N:
        for a in A:
            cost = num_cost[a]
            if N-cost>=0 and dp[N-cost]==dp[N]-1: 
                ans.append(a)
                N-=cost
                break
    print(*ans,sep="")



if __name__ == '__main__':
    main()

Solution (Python):
def is_big(x = [0]*10, y = [0]*10):
    if sum(x) > sum(y):
        return True
    if sum(x) < sum(y):
        return False
    for i in range(0,10)[::-1]:
        if x[i] > y[i]:
            return True
        if y[i] > x[i]:
            return False
    return True
  
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))

d = [0]*8
b = []
L1 = [1,7,4,2,3,5,6,9,8]
L2 = [2,3,4,5,5,5,6,6,7]
for i in range(9):
  if L1[i] in a:
    d[L2[i]] = L1[i]
    if L2[i] not in b:
      b.append(L2[i])


p = []
for i in range(n+1):
  p.append([-1,0,0,0,0,0,0,0,0,0])
  
p[0][0] = 0
for i in range(1,n+1):
  for t in b:
    if i-t <0 or p[i-t][0] == -1: 
      continue
    q = p[i-t][:]
    q[d[t]] += 1
    if is_big(q,p[i]):
      p[i] = q

a = ""
for i in range(10)[::-1]:
  a += str(i)*p[n][i]
print(a)

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = {a: d[a] for a in A}
m = min(D.values())
E = {}
for k, v in D.items():
    v -= m
    if v in E:
        E[v] = max(E[v], k)
    else:
        E[v] = k
F = sorted(E.keys(), key=lambda f: (max(0, E[f]-E[0]), f), reverse=True)
F.remove(0)
K = N // m
for k in range(K, 0, -1):
    B = [E[0]] * k
    R = N - k * m
    if not R:
        print("".join(map(str, sorted(B, reverse=True))))
        break
    def rec(r, i, j):
        if i < 0:
            return
        for f in F[j:]:
            if r == f:
                B[i] = E[f]
                print("".join(map(str, sorted(B, reverse=True))))
                exit()
            elif r > f:
                B[i], tmp = E[f], B[i]
                rec(r - f, i - 1, j)
                B[i] = tmp
            j += 1
    rec(R, k-1, 0)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


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

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



dp = [(0, [0] * 9) for _ in range(N + 10)]
for i in range(N):
    d, counts = dp[i]
    if i > 0 and d == 0:
        continue
    for a in A:
        cnts = counts[:]
        cnts[-a] += 1
        dp[i + requires[a]] = max(dp[i + requires[a]], (d + 1, cnts))
ans = ''
for i, cnt in enumerate(dp[N][1]):
    ans += str(9 - i) * cnt
print(ans)

Solution (Python):
N, M = map(int, input().split())
A = map(int, input().split())
ok = [0] * 10
for a in A: ok[a] = 1

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

for i in range(N):
    for num in range(1, 10):
        c = cost[num]
        if ok[num] == 0 or i + c > N: continue
        dp[i+c] = max(dp[i+c], dp[i] * 10 + num)

ans = dp[N]
print(ans)

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):
  if dp[i] == -1: continue
  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[-1])

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

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

for n_i in range(n):
  for a_i in A:
    if n_i+C[a_i]<=n:
      dp[n_i+C[a_i]] = max(dp[n_i+C[a_i]], dp[n_i]*10+a_i)
      
print(dp.pop())

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
W = [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 + W[a] < N + 1:
            dp[i + W[a]] = max(dp[i + W[a]], dp[i]*10 + a)
print(dp[N])

Solution (Python):
def p_d():
    n, m = map(int, input().split())
    a = map(int, input().split())
    c = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    inf = 10 ** 9
    costs = {m: c[m - 1] for m in a}
    
    dp = [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)
    num = n
    result = []
    for _ in range(dp[n]):
        for digit in digits:
            if num >= costs[digit] and dp[num - costs[digit]] != -inf and dp[num - costs[digit]] == dp[num] - 1:
                result.append(str(digit))
                num -= costs[digit]
                break
    print("".join(result))


if __name__ == '__main__':
    p_d()

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


if __name__ == "__main__":
    main()

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):
    if dp[i] == -1:continue
    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[-1])

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
w=[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+w[a]<N+1:
      dp[i+w[a]]=max(dp[i+w[a]],dp[i]*10+a)
      
print(dp[-1])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

def compare(a, b):
    if a is None:
        return b
    if len(a) > len(b):
        return a
    if len(a) < len(b):
        return b
    return max(a, b)

N, M = MAP()
A = LIST()


dp = [None] * (N+1)
dp[0] = ''
for i in range(N):
    if dp[i] is None:
        continue
    for j in A:
        cnt = tocnt[j]
        if i+cnt <= N:
            dp[i+cnt] = compare(dp[i+cnt], dp[i] + str(j))
print(dp[N])

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

print(dp[n])

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

Solution (Python):
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = [0 for i in range(N+1)]
ans = 0
tmp = set()
tmp.add(0)
for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = 1 + dp[i-k]
            tmp.add(i)
            break


num.sort(reverse=True)
tmp = N
ans = []
for i in reversed(range(1, dp[N])):
    for n, k in num:
        if dp[tmp - k] == i:
            ans.append(n)
            tmp -= k
            break
for n, k in num:
    if k == tmp:
        ans.append(n)
        break

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

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

t = ['_', 2, 5, 5, 4, 5, 6, 3, 7, 6]


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

for a in aa:
    for i in range(len(dp)):
        if dp[i] >= 0 and i + t[a] < len(dp):
            dp[i + t[a]] = max(dp[i + t[a]], dp[i] * 10 + a)

print(dp[n])

Solution (Python):
import os, sys, re, math
sys.setrecursionlimit(100000)
N,M = list(map(int,input().split(' ')))
A = list(map(int,input().split(' ')))

match = [100,2,5,5,4,5,6,3,7,6]
memo = {}

def doit(m):
    if m in memo:
        return memo[m]
    if m == 0:
        return ""

    ret = None
    for a in A:
        tmp = None
        if m - match[a] >= 0:
            tmp = doit(m - match[a])
            if tmp is not None:
                tmp = str(a) + tmp
                if ret is not None:
                    if len(ret) < len(tmp) or (len(ret) == len(tmp) and tmp > ret):
                        ret = tmp
                else:
                    ret = tmp

    memo[m] = ret
    return ret

print(doit(N))

Solution (Python):
inf = 1 << 20
need = -1, 2, 5, 5, 4, 5, 6, 3, 7, 6

n, m = map(int, input().split())
a = map(int, input().split())
d = {need[x]: x for x in sorted(a)}  
e = tuple(sorted(d.items(), key=lambda x: x[1], reverse=True))  

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


for j in range(1, n + 1):
    dp[j] = max((dp[j - cnt] for cnt, _ in e if j - cnt >= 0), default=-inf) + 1

ret = []
r = dp[n]

curr = n
while r > 0:
    for cnt, num in e:
        if curr - cnt >= 0 and dp[curr - cnt] == r - 1:
            ret.append(num)
            r -= 1
            curr -= cnt
            break

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

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):
    if dp[i] == -1:continue
    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()))
weight=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0]=0

for i in range(N+1):
    if dp[i] == -1:continue
    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()))
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 = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True

def f(nokori, current):
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)


def hoge():
  for key, nums in list(d.items()):
      for num in nums:
        if enable[num]:
          return (num, key)
num, key = hoge()
cs = []
while n > 50:
  n -= key
  cs.append(str(num))


num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Solution (Python):
NUM = (None, 2, 5, 5, 4, 5, 6, 3, 7, 6)

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


dp = [0] * (nSticks + 1)
for digit in a:
    if NUM[digit] <= nSticks:
        dp[NUM[digit]] = max(dp[NUM[digit]], digit)
for sticks in range(2, nSticks + 1):
    for digit in a:
        if sticks - NUM[digit] >= 0 and dp[sticks - NUM[digit]] > 0:
            dp[sticks] = max(dp[sticks], dp[sticks - NUM[digit]] * 10 + digit)
print(dp[-1])

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
matches = [100, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [""]
for i in range(1, n + 1):
    dp.append(None)
    for d in a:
        m = matches[d]
        if i - m >= 0 and dp[i - m] is not None:
            r = max(dp[i - m] + str(d), str(d) + dp[i - m])
            if dp[i] is None or len(r) > len(dp[i]) or len(r) == len(dp[i]) and r > dp[i]:
                dp[i] = r
print(dp[n])

Solution (Python):
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True

def f(nokori, current):
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)


hoge = False
for key, nums in list(d.items()):
    
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))


num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Solution (Python):
import sys

sys.setrecursionlimit(100000)

n, m = map(int, input().split())
a = list(map(int, input().split()))
memo = {}
matches = [100, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def doit(n):
    if n == 0:
        return ""
    if not n in memo:
        ret = None
        for d in a:
            m = matches[d]
            if n - m >= 0 and doit(n - m) is not None:
                r = max(doit(n - m) + str(d), str(d) + doit(n - m))
                if ret is None or len(r) > len(ret) or len(r) == len(ret) and r > ret:
                    ret = r
        memo[n] = ret
    return memo[n]

print(doit(n))

Solution (Python):
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
memo = {}

def f(nokori, current):
  k = (nokori, current)
  if k in memo:
    return memo[k]
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]


hoge = False
for key, nums in list(d.items()):
    
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:
  n -= key
  cs.append(str(num))


num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Solution (Python):
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}

d[2] = [1]

d[3] = [7]

d[4] = [4]



d[5] = [5, 3, 2]


d[6] = [9, 6]

d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
memo = {}
def f(nokori, current):

  k = (nokori, current)  
  if k in memo:
    return memo[k]
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]


hoge = False
for key, nums in list(d.items()):
    
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 50:  
  n -= key
  cs.append(str(num))
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
nums=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for x in a:
        if i-nums[x]>=0:
            dp[i]=max(dp[i-nums[x]]+1,dp[i])
k=dp[n]
ans=[]
for i in range(k):
    for x in a:
        if n-nums[x]<0:
            continue
        if dp[n-nums[x]]==dp[n]-1:
            n-=nums[x]
            ans.append(x)
            break
print("".join(list(map(str,ans))))

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

x = [-float('inf')] * (n + 1)
x[0] = 0
l = [0] * (n + 1)
_c = [2,5,5,4,5,6,3,7,6]
c = dict()
for i in range(m):
    c[a[i]] = _c[a[i] - 1]

for i in range(1, n + 1):
    x_max = -float('inf')
    l_max = 0
    for digit in c.keys():
        left = i - c[digit]
        if left >= 0:
            tmp_x = digit * (10 ** l[left]) + x[left]
            tmp_l = l[left] + 1
            if tmp_x > x_max:
                x_max = tmp_x
                l_max = tmp_l

    x[i] = x_max
    l[i] = l_max
print(x[-1])

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

NUM = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
INF = 10**14

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

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

D = dp[N]
ind = N
ans = ''
for _ in range(D):
    for a in A:
        c = NUM[a]
        if ind - c < 0: continue
        if dp[ind] == dp[ind-c] + 1:
            ind -= c
            ans += str(a)
            break
print(ans)

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[]
for i,j in((7,3),(9,6),(8,7),(6,6),(5,5),(4,4),(3,5),(1,2),(2,5)):
    if i in a:
        d.append((i,j))
dp=[0]*-~n
for i in range(1,n+1):
    for j,k in d:
        if i-k<0 or i-k!=0 and not dp[i-k]:continue
        dp[i]=max(dp[i],dp[i-k]*10+j)
print(dp[n])

Solution (Python):
import copy


n,m = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
dict = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dict2 = {1:1, 2:10**4, 3:10**8, 4:10**12, 5:10**16, 6:10**20, 7:10**24, 8:10**28, 9:10**32}
bonus = 10**36
l = []
for i in a:
    l.append((i,dict[i],dict2[i]))

dp = [[['n',0,[]] for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
    dp[i][0][0] = "t"
for i in range(1,m+1):
    num = l[i-1][0]
    c = l[i-1][1]
    v = l[i-1][2]
    for j in range(1, n+1):
        if (j-c < 0 or dp[i][j-c][0] == 'n') and dp[i-1][j][0] == 'n':
            continue
        elif (j-c < 0 or dp[i][j-c][0] == 'n'):
            dp[i][j] = copy.copy(dp[i-1][j])
        elif dp[i-1][j][0] == 'n':
            dp[i][j][0] = 't'
            dp[i][j][1] = dp[i][j-c][1] + v + bonus
            dp[i][j][2] = copy.copy(dp[i][j-c][2])
            dp[i][j][2].append(num)
        else:
            dp[i][j][0] = 't'
            if dp[i-1][j][1] >= dp[i][j-c][1]+v+bonus:
                dp[i][j] = copy.copy(dp[i-1][j])
            else:
                dp[i][j][1] = dp[i][j-c][1]+v+bonus
                dp[i][j][2] = copy.copy(dp[i][j-c][2])
                dp[i][j][2].append(num)
L = dp[m][n][2]
L = sorted(L, reverse=True)
ans = ''
for i in range(len(L)):
    ans += str(L[i])
print(int(ans))

Solution (Python):

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



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

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

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

for i in range(N):
	for m in A:
		need = mnum[m]
		if(dp[i] >= 0):
			dp[i+need] = max(dp[i+need], dp[i] * 10 + m);

print(dp[N])

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

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]


INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

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

answer = []
for i in A:
    x = table[i]
    while N - x >= 0 and dp[N] == dp[N - x] + 1:
        answer.append(i)
        N -= x

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

Solution (Python):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

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

n, m = ril()
ls = ril()

d = collections.defaultdict(int)
for x in ls:
    d[d0[x]] = max(x, d[d0[x]])

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

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
mm=[0,2,5,5,4,5,6,3,7,6]

dp=[0]
m = [mm[i] for i in range(10) if i in a]
for i in range(1,n+1):
    tres=[-10**10]
    for sm in m:
        if i - sm >= 0:
            tres.append(dp[i-sm]+1)
    dp.append(max(tres))
k=dp[n]
res = []
a.sort(reverse=True)
while n > 0:
    for sa in a:
        if n-mm[sa] >= 0 and dp[n-mm[sa]]==dp[n]-1:
            res.append(sa)
            n -= mm[sa]
            break

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

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:
            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 = sorted(list(map(int, input().split())), reverse = True)

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

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

dp[0] = 0
for idx in range(1,N+1):
    tmp = []
    for x in A:
        if idx - n_match[x] >= 0:
            tmp.append(dp[idx - n_match[x]] + 1)
    if tmp:
        dp[idx] = max(tmp)

ans = ""
rest_match = N
while len(ans) <= N//2 and rest_match > 0:
    for x in A:
        if rest_match - n_match[x] >= 0 and dp[rest_match - n_match[x]] == dp[rest_match] - 1:
            ans += str(x)
            rest_match -= n_match[x]
            break
            
print(ans)

Solution (Python):
from bisect import bisect_left
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort(reverse=True)

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

makeDigit = [-float('inf')] * (N + 1)
makeDigit[0] = 0
for n in range(1, N + 1):
    d = makeDigit[n]
    for k in nums:
        cnt = n - matchNum[k]
        if cnt >= 0:
            d = max(d, makeDigit[cnt] + 1)
    if makeDigit[n] < d:
        makeDigit[n] = d

ans = []
for d in range(makeDigit[N])[:: -1]:
    for k in nums:
        cnt = N - matchNum[k]
        if cnt >= 0 and makeDigit[cnt] == d:
            ans.append(k)
            N = cnt
            break

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

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

need = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (N + 10)
dp[0] = 0
for i in range(N) :
    if dp[i] < 0 :
        continue
        
    for j in A :
        dp[i+need[j]] = max(dp[i+need[j]], dp[i]*10+j)
        
print(dp[N])

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):
def main():
    N, M, *A = map(int, open(0).read().split())

    C = [0, 1, 4, 4, 3, 4, 5, 2, 6, 5]

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

    print(dp[N])

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M, *A = map(int, open(0).read().split())

    C = [0, 1, 4, 4, 3, 4, 5, 2, 6, 5]

    dp = [0] * N + [-1] * 6
    for i in range(N):
        dp[i + 1] = max(dp[i - C[a]] * 10 + a for a in A)

    print(dp[N])

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M, *A = map(int, open(0).read().split())

    C = [0, 1, 4, 4, 3, 4, 5, 2, 6, 5]

    dp = [0] * N + [-1] * 9
    for i in range(N):
        dp[i + 1] = max(a + 10 * dp[i - C[a]] for a in A)

    print(dp[N])

if __name__ == '__main__':
    main()

Solution (Python):
N, M, *A = map(int, open(0).read().split())

C = [0, 1, 4, 4, 3, 4, 5, 2, 6, 5]

dp = [0] * N + [-1] * 9
for i in range(N):
    dp[i + 1] = max(a + 10 * dp[i - C[a]] for a in A)

print(dp[N])

Solution (Python):
N,M=map(int,input().split())
n=[0,1,2,3,4,5,6,7,8,9]
H=[0,2,5,5,4,5,6,3,7,6]

L=[]
A=list(map(int,input().split()))
A.sort(reverse=True)

for i in range(M):
    for j in range(10):
        if A[i]==n[j]:
            L.append([H[j],n[j]])

dp=["" for i in range(N+1)]
dp[0]="0"
for i in range(len(L)):
    for j in range(L[i][0],N+1):
        if dp[j-L[i][0]]!="":
            if len(dp[j])>len(dp[j-L[i][0]]+str(L[i][1])):
                continue
            elif len(dp[j])<len(dp[j-L[i][0]]+str(L[i][1])):
                dp[j]=dp[j-L[i][0]]+str(L[i][1])
            else:
                if dp[j]<dp[j-L[i][0]]+str(L[i][1]):
                    dp[j]=dp[j-L[i][0]]+str(L[i][1])
print(dp[N][1:])

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+9)
d=[0,2,5,5,4,5,6,3,7,6]
for i in range(n+1):
  for j in a:
    if dp[i]or i<1:dp[i+d[j]]=max(dp[i+d[j]],dp[i]*10+j)
print(dp[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:
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)
print(dp[n])
'''
    dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
    a=sorted(list(map(int,input().split())),key=lambda x:(dic[x],-x))
    b=[0]*10
    i=0
    while(n!=0):
        b[a[i]]+=1
        n-=dic[a[i]]
        if n<dic[a[i]] and n!=0:
            while(n<dic[a[i+1]]):
                b[a[i]]-=1
                n+=dic[a[i]]
            i+=1
    print(a)
    print(b)
'''

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

a.sort()
a.reverse()
ans=[]
y=n
for i in range(dp[n],0,-1):
  for j in range(m):
    if y-x[a[j]-1]>=0:
      if dp[y-x[a[j]-1]]>=i-1:
        ans.append(str(a[j]))
        y-=x[a[j]-1]
        break
print(''.join(ans))