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



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
d={2:0,3:0,4:0,5:0,6:0,7:0}
for i in A:
    if i==1:
        d[2]=1
    elif i==7:
        d[3]=7
    elif i==8:
        d[7]=8
    elif i==4:
        d[4]=4
    elif i==6 or i==9:
        if d[6]<i:
            d[6]=i
    else:
        if d[5]<i:
            d[5]=i
l=[]
for i in d.keys():
    if d[i]:
        l.append(i)
l.sort()
a=[]
m=0
if len(l)>=4:
    for i in range(4):
        for j in range(4):
            for k in range(4):
                t=N-i*l[1]-j*l[2]-k*l[3]
                if t%l[0] or t<0:
                    continue
                ke=i+j+k+t//l[0]
                if ke<m:
                    continue
                else:
                    s=[d[l[1]]]*i+[d[l[2]]]*j+[d[l[3]]]*k+[d[l[0]]]*(t//l[0])
                    s.sort(reverse=1)
                    if ke==m:
                        a.append(s)
                    else:
                        a=[s]
                        m=ke
    print(*max(a),sep="")
elif len(l)==3:
    for i in range(5):
        for j in range(5):
            t=(N-i*l[1]-j*l[2])
            if t%l[0] or t<0:
                continue
            ke=i+j+t//l[0]
            if ke<m:
                continue
            else:
                s=[d[l[1]]]*i+[d[l[2]]]*j+[d[l[0]]]*(t//l[0])
                s.sort(reverse=1)
                if ke==m:
                    a.append(s)
                else:
                    a=[s]
                    m=ke
    print(*max(a),sep="")
elif len(l)==2:
    for i in range(6):
        if (N-l[1]*i)%l[0]==0:
            a=[d[l[1]]]*i+[d[l[0]]]*((N-i*l[1])//l[0])
            a.sort(reverse=1)
            print(*a,sep="")
            break
else:
    a=d[l[0]]*(N//l[0])
    print(*a,sep="")

Submission status: Runtime Error

Solution code:
n, m = map(int,raw_input().split(' '))
ais= map(int, raw_input().split(' '))

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

cost  = {i+1:v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

def f(c,dp,suffix):
	a = dp[c] if dp[c] is not None else ()
	if len(a) > suffix + 1:
		return a
	b = tuple(sorted(list((digit,) + suffix))[::-1])
	if len(b) > len(a): return b
	return max(a,b)
	
for c in range(1,n + 1):
	for digit in ais:
		if c >= cost[digit] and dp[c-  cost[digit]] is not None:
			dp[c] = f(c,dp,dp[c-cost[digit]]) 
print ''.join(map(str,list(dp[n])))

Submission status: Runtime Error

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    required = [None]+[2,5,5,4,5,6,3,7,6]
    dp = [0 for _ in range(N+1)]
    candidates = {}
    for a in A:
        req = required[a]
        if dp[req] < a:
            dp[req] = a
            candidates[req] = a
    #print(dp)
    #print(candidates)
    for i in range(N+1):
        for n_match, num in candidates.items():
            if i - n_match >= 0 and dp[i-n_match] != 0:
                dp[i] = max(dp[i], dp[i-n_match]*10+num)
    #print(dp)
    print(dp[N])

if '__main__' == __name__:
    resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    required = [10**18]+[2,5,5,4,5,6,3,7,6]
    dp = [0 for _ in range(N+1)]
    candidates = {}
    for a in A:
        req = required[a]
        if dp[req] < a:
            dp[req] = a
            candidates[req] = a
    #print(dp)
    #print(candidates)
    for i in range(N+1):
        for n_match, num in candidates.items():
            if i - n_match >= 0 and dp[i-n_match] != 0:
                dp[i] = max(dp[i], int(str(dp[i-n_match])+str(num)))
    #print(dp)
    print(dp[N])

if '__main__' == __name__:
    resolve()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
memo = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [''] * (n + 1)
for aa in a:
    if aa <= n:
        if dp[memo[aa]] < str(aa):
            dp[memo[aa]] = str(aa)
for i in range(n):
    if dp[i] == '':
        continue
    for aa in a:
        if i + memo[aa] <= n:
            v = str(aa) + dp[i]
            if len(dp[i + memo[aa]]) < len(v):
                dp[i + memo[aa]] = v
            else:
                dp[i + memo[aa]] = max(dp[i + memo[aa]], v)
print(dp[-1])

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
memo = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] * (n + 1)
for aa in a:
    dp[memo[aa]] = max(dp[memo[aa]], aa)
for i in range(n):
    if dp[i] == 0:
        continue
    for aa in a:
        if i + memo[aa] <= n:
            v = int(str(aa) + str(dp[i]))
            if dp[i + memo[aa]] < v:
                dp[i + memo[aa]] = v
print(dp[-1])

Submission status: Runtime Error

Solution code:
def main():
    n, m, *a = map(int, open(0).read().split())
    t = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    a.sort(reverse=True)

    dp = [-float('Inf')] * (n + 1)
    dp[0] = 0
    for i in range(2, n + 1):
        for j in a:
            dp[i] = max(dp[i], dp[i - t[j]] + 1)

    nums = []
    k = dp[n]
    while n:
        for x in a:
            if dp[n - t[x]] == k - 1:
                nums.append(x)
                n -= t[x]
                break
        k -= 1

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
List = list(map(int,input().split()))

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

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ 0 for j in range(X+1)]  for i in range(M)]

  for i in range(M):
    for j in range(X):
      if kazu[i] <= j:
        dp[i][j+1] = max(dp[i][j+1-kazu[i]] + 1,dp[i-1][j+1])
      else:
        dp[i][j+1] = dp[i-1][j+1]
  return dp[-1]
   
keta_arr = dddd(kazu,N)
keta = keta_arr[-1]
List.sort(reverse=True)
ans = []
x = 0

while keta>0:
  for aa in List:
    k = a[aa]
    if N-k >= 0:
      if keta_arr[-k-1-x] == keta-1:
        ans.append(aa)
        x += k
        N = N-k
        keta -= 1
    else:
      continue
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
List = list(map(int,input().split()))

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

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ 0 for j in range(X+1)]  for i in range(M)]

  for i in range(M):
    for j in range(X):
      if kazu[i] <= j:
        dp[i][j+1] = max(dp[i][j+1-kazu[i]] + 1,dp[i-1][j+1])
      else:
        dp[i][j+1] = dp[i-1][j+1]
  return dp[-1]
   
keta_arr = dddd(kazu,N)
keta = keta_arr[-1]
List.sort(reverse=True)
ans = []
x = 0

for i in range(keta):
  for aa in List:
    k = a[aa]
    if N-k >= 0:
      if keta_arr[-k-1-x] == keta-i-1:
        ans.append(aa)
        x += k
        N = N-k
    else:
      continue
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
List = list(map(int,input().split()))

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

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ 0 for j in range(X+1)]  for i in range(M)]

  for i in range(M):
    for j in range(X):
      if kazu[i] <= j:
        dp[i][j+1] = max(dp[i][j+1-kazu[i]] + 1,dp[i-1][j+1])
      else:
        dp[i][j+1] = dp[i-1][j+1]
  return dp[-1]
   
keta_arr = dddd(kazu,N)
keta = keta_arr[-1]
List.sort(reverse=True)
ans = []
x = 0

for i in range(keta):
  d = 0
  for aa in List:
    k = a[aa]
    if N-k > 0:
      if keta_arr[-k-1-x] == keta-i-1 and keta-i-1 != 0 and d == 0:
        ans.append(aa)
        d = 1
        x += k
        N = N-k
        if N == 0:
          break
        continue
    elif N == k and keta-i-1 == 0 and d == 0:
      ans.append(aa)
      d = 1
      N = 0
  if N == 0:
    break
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
List = list(map(int,input().split()))

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

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ 0 for j in range(X+1)]  for i in range(M)]

  for i in range(M):
    for j in range(X):
      if kazu[i] <= j:
        dp[i][j+1] = max(dp[i][j+1-kazu[i]] + 1,dp[i-1][j+1])
      else:
        dp[i][j+1] = dp[i-1][j+1]
  return dp[-1]
   
keta_arr = dddd(kazu,N)
keta = keta_arr[-1]
List.sort(reverse=True)
ans = []
x = 0

for i in range(keta):
  for aa in List:
    k = a[aa]
    if N-k > 0:
      if keta_arr[-k-1-x] == keta-i-1 and keta-i-1 != 0:
        ans.append(aa)
        x += k
        N = N-k
        if N == 0:
          break
        continue
    elif N == k and keta-i-1 == 0:
      ans.append(aa)
      N = 0
  if N == 0:
    break
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
List = list(map(int,input().split()))

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

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ 0 for j in range(X+1)]  for i in range(M)]

  for i in range(M):
    for j in range(X):
      if kazu[i] <= j:
        dp[i][j+1] = max(dp[i][j+1-kazu[i]] + 1,dp[i-1][j+1])
      else:
        dp[i][j+1] = dp[i-1][j+1]
  return dp[-1][-1]
   
keta = dddd(kazu,N)
List.sort(reverse=True)
ans = []

for i in range(keta):
  for aa in List:
    k = a[aa]
    if N-k > 0:
      if dddd(kazu,N-k) == keta-i-1 and keta-i-1 != 0:
        ans.append(aa)
        N = N-k
        if N == 0:
          break
        continue
    elif N == k and keta-i-1 == 0:
      ans.append(aa)
      N = 0
  if N == 0:
    break
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))

Submission status: Runtime Error

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

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

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

for i in range(N):
    for j in A:
        if i+B[j] <= N:
            DP[i+B[j]] = max(DP[i]*10+j, DP[i+B[j]])

print(DP[N+1])

Submission status: Runtime Error

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

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

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

for i in range(N):
    for j in A:
        if i+B[j] <= N:
            DP[i+B[j]] = max(DP[i]*10+i,DP[i+B[j]])

print(DP[N+1])

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
List = list(map(int,input().split()))

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

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ 0 for j in range(X+1)]  for i in range(M)]

  for i in range(M):
    for j in range(X):
      if kazu[i] <= j:
        dp[i][j+1] = max(dp[i][j+1-kazu[i]] + 1,dp[i-1][j+1])
      else:
        dp[i][j+1] = dp[i-1][j+1]
  return dp[-1][-1]
   
keta = dddd(kazu,N)
List.sort(reverse=True)
ans = []

for i in range(keta):
  for aa in List:
    k = a[aa]
    if N-k > 0:
      if dddd(kazu,N-k) == keta-i-1:
        ans.append(aa)
        N = N-k
        if N == 0:
          break
        continue
    elif N == k and keta-i-1 == 1:
      ans.append(aa)
      N = 0
  if N == 0:
    break
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))

Submission status: Runtime Error

Solution code:
# D - Match Matching

N, M = map(int, input().split())
A = list(int(x) for x in input().split())
match_list = [(0, 6), (1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
MA = []
for a in A:
    MA.append(MATCH[a])
MA.sort(key=lambda x: x[1])

def dfs(tmp, s):
    global ans
    if s == N:
        ans = max(ans, tmp)    
    for ma in MA:
        if s+ma[1] <= N:
            tmp = tmp*10 + ma[0]
            dfs(tmp, s + ma[1])
            tmp //= 10

tmp = 0
ans = 0
dfs(tmp, 0)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import Dict, List
except ImportError:
    pass


def solve(N: int, M: int, A: "List[int]"):
    mn = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort(reverse=True)
    dp = [-1] * (N + 1)
    dp[0] = 0
    for i in range(1, N + 1):
        m = -1
        for Ai in A:
            if i - mn[Ai] >= 0 and dp[i - mn[Ai]] >= 0:
                m = max(m, dp[i - mn[Ai]] + 1)
        if m >= 0:
            dp[i] = m
    assert dp[N] >= 0
    k = N
    res = []  # type: List[int]
    while dp[k]:
        for Ai in A:
            if dp[k - mn[Ai]] == dp[k] - 1:
                res.append(Ai)
                k -= mn[Ai]
                break

    print("".join(str(d) for d in res))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def num_to_match(n):
    if n == 1:
        return 2
    elif n == 7:
        return 3
    elif n == 4:
        return 4
    elif n in [2, 3, 5]:
        return 5
    elif n in [6, 9]:
        return 6
    else:
        return 7


def max_length(N, match):
    match = set(match)
    INF = 10**15
    dp = [- INF for _ in range(N + 1)]
    dp[0] = 0
    for n in range(1, N + 1):
        max_l = dp[n]
        for m in match:
            if n - m >= 0:
                max_l = max([max_l, 1 + dp[n - m]])
        dp[n] = max_l
    return dp


def main():
    N, _ = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    A.sort(reverse=True)
    match = list(map(num_to_match, A))
    max_l = max_length(N, match)
    digits = [0 for _ in range(max_l[N])]
    n_match = N
    for i in range(max_l[N]):
        for a in A:
            ma = num_to_match(a)
            if max_l[n_match - ma] == max_l[n_match] - 1:
                digits[i] = a
                n_match -= ma
                break
    ans = 0
    for d in digits:
        ans *= 10
        ans += d
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def num_to_match(n):
    if n == 1:
        return 2
    elif n == 7:
        return 3
    elif n == 4:
        return 4
    elif n in [2, 3, 5]:
        return 5
    elif n in [6, 9]:
        return 6
    else:
        return 7


def match_to_max_num(m, A):
    if m == 2:
        return 1
    elif m == 3:
        return 7
    elif m == 4:
        return 4
    elif m == 5:
        return max(set({2, 3, 5}).intersection(set(A)))
    elif m == 6:
        return max(set({6, 9}).intersection(set(A)))
    else:
        return 8


def find_opt_match(N, match):
    match_list = [0 for _ in range(N)]
    def dfs(cur, rest, m=0):
        if rest < m:
            return False
        if rest == m:
            match_list[cur] = m
            return True
        for mm in match:
            if dfs(cur + 1, rest - m, mm):
                if cur >= 0:
                    match_list[cur] = m
                return True
        return False
    dfs(-1, N)
    return match_list[:match_list.index(0)]


def main():
    N, M = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    match = list(map(num_to_match, A))
    match.sort()
    opt_match = find_opt_match(N, match)
    opt_num = list(map(lambda x: match_to_max_num(x, A), opt_match))
    opt_num.sort()
    ans = 0
    pw = 1
    for n in opt_num:
        ans += n * pw
        pw *= 10
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
INF = 1 << 30

def main():
    N,M = map(int,input().split())
    A = set(map(str,input().split()))
    number = '174532968'
    necesary_match = (2,3,4,5,5,5,6,6,7)
    match = {i:j for i,j in zip(number,necesary_match)}

    if '1' in A:
        if N%2 == 0:
            ans = ['1'] * (N//2)
        else:
            for num in '75328':
                if num in A:
                    ans = ['1'] * ((N - match[num])//2) + [num]
                    break
    elif '7' in A:
        if N%3 == 0:
            ans = ['7'] * (N//3)
        elif N%3 == 1:
            flag = False
            for num in '48':
                if num in A:
                    flag = True
                    ans = ['7'] * ((N - match[num])//3) + [num]
                    break
            if not flag:
                for num in '532':
                    if num in A:
                        ans = ['7'] * ((N - 2*match[num])//3) + [num] * 2
                        break
        else:
            flag = False
            for num in '532':
                if num in A:
                    flag = True
                    ans = ['7'] * ((N - match[num])//3) + [num]
                    break
            if not flag:
                for num in '48':
                    if num in A:
                        ans = ['7'] * ((N - 2*match[num])//3) + [num] * 2
                        break
    elif '4' in A:
        if N%4 == 0:
            ans = ['4'] * (N//4)
        elif N%4 == 1:
            flag = False
            for num in '532':
                if num in A:
                    flag = True
                    ans = ['4'] * ((N - match[num])//4) + [num]
                    break
            if not flag:
                for num in '96':
                    if num in A:
                        flag = True
                        ans = ['4'] * ((N - match[num] - match['8'])//4) + [num,'8']
                        break
            if not flag:
                ans = ['4'] * ((N - match['8']*3)//4) + ['8'] * 3
        elif N%4 == 2:
            flag = False
            for num in '96':
                if num in A:
                    ans = ['4'] * ((N - match[num])//4) + [num]
                    flag = True
                    break
            if not flag:
                for num in '532':
                    if num in A:
                        ans = ['4'] * ((N - 2*match[num])//4) + [num] * 2
                        flag = True
                        break
            if not flag:
                ans = ['4'] * ((N - 2*match['8'])//4) + ['8'] * 2
        else:
            flag = False
            if '8' in A:
                flag = True
                ans = ['4'] * ((N - match['8'])//4) + ['8']
            if not flag:
                x = ''
                for num in '96':
                    if num in A:
                        x = num
                        break
                y = ''
                for num in '532':
                    if num in A:
                        y = num
                        break
                if x:
                    ans = ['4'] * ((N - match[x] - match[y])//4) + [x,y]
                else:
                    ans = ['4'] * ((N - 3*match[y])//4) + [y] *3
    else:
        x = ''
        for num in '532':
            if num in A:
                x = num
                break
        if x:
            if N%5 == 0:
                ans = [x] * (N//5)
            elif N&5 == 1:
                flag = False
                for num in '96':
                    if num in A:
                        flag = True
                        ans = [x] * ((N - match[num])//5) + [num]
                        break
                if not flag:
                    ans = [x] * ((N - 3*match['8'])//5) + ['8'] * 3
            elif N%5 == 2:
                if '8' in A:
                    ans = [x] * ((N - match['8'])//5) + ['8']
                else:
                    for num in '96':
                        if num in A:
                            ans = [x] * ((N - 2*match[num])//5) + [num] * 2
                            break
            elif N%5 == 3:
                if '8' in A:
                    flag = False
                    for num in '96':
                        if num in A:
                            flag = True
                            ans = [x] * ((N - match[num] - match['8'])//5) + ['8',num]
                            break
                    if not flag:
                        ans = [x] * ((N - 4*match['8'])//5) + ['8'] * 4
                else:
                    for num in '96':
                        if num in A:
                            ans = [x] * ((N - 3*match[num])//5) + [num] * 3
                            break
            elif N%5 == 4:
                if '8' in A:
                    ans = [x] * ((N - 2*match['8'])//5) + ['8'] * 2
                else:
                    for num in '96':
                        if num in A:
                            ans = [x] * ((N - 4*match[num])//5) + [num] * 4
                            break

        else:
            y = ''
            for num in '96':
                if num in A:
                    y = num
                    break
            if y:
                if N%6 == 0:
                    ans = [y] * (N//6)
                else:
                    k = N%6
                    ans = [y] * ((N - k*match['8'])//6) + ['8'] * k
            else:
                ans = ['8'] * (N//7)
    ans.sort(reverse = True)
    print(''.join(ans))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
INF = 1 << 30

def main():
    N,M = map(int,input().split())
    A = set(map(str,input().split()))
    number = '174532968'
    necesary_match = (2,3,4,5,5,5,6,6,7)
    match = {i:j for i,j in zip(number,necesary_match)}

    if '1' in A:
        if N%2 == 0:
            ans = ['1'] * (N//2)
        else:
            for num in '75328':
                if num in A:
                    ans = ['1'] * ((N - match[num])//2) + [num]
                    break
    elif '7' in A:
        if N%3 == 0:
            ans = ['7'] * (N//3)
        elif N%3 == 1:
            flag = False
            for num in '48':
                if num in A:
                    flag = True
                    ans = ['7'] * ((N - match[num])//3) + [num]
                    break
            if not flag:
                for num in '532':
                    if num in A:
                        ans = ['7'] * ((N - 2*match[num])//3) + [num] * 2
                        break
        else:
            flag = False
            for num in '532':
                if num in A:
                    flag = True
                    ans = ['7'] * ((N - match[num])//3) + [num]
                    break
            if not flag:
                for num in '48':
                    if num in A:
                        ans = ['7'] * ((N - 2*match[num])//3) + [num] * 2
                        break
    elif '4' in A:
        if N%4 == 0:
            ans = ['4'] * (N//4)
        elif N%4 == 1:
            flag = False
            for num in '532':
                if num in A:
                    flag = True
                    ans = ['4'] * ((N - match[num])//4) + [num]
                    break
            if not flag:
                for num in '96':
                    if num in A:
                        flag = True
                        ans = ['4'] * ((N - match[num] - match['8'])//4) + [num,'8']
                        break
            if not flag:
                ans = ['4'] * ((N - match['8']*3)//4) + ['8'] * 3
        elif N%4 == 2:
            flag = False
            for num in '96':
                if num in A:
                    ans = ['4'] * ((N - match[num])//4) + [num]
                    flag = True
                    break
            if not flag:
                for num in '532':
                    if num in A:
                        ans = ['4'] * ((N - 2*match[num])//4) + [num] * 2
                        flag = True
                        break
            if not flag:
                ans = ['4'] * ((N - 2*match['8'])//4) + ['8'] * 2
        else:
            flag = False
            if '8' in A:
                flag = True
                ans = ['4'] * ((N - match['8'])//4) + ['8']
            if not flag:
                x = ''
                for num in '96':
                    if num in A:
                        x = num
                        break
                y = ''
                for num in '532':
                    if num in A:
                        y = num
                        break
                if x:
                    ans = ['4'] * ((N - match[x] - match[y])//4) + [x,y]
                else:
                    ans = ['4'] * ((N - 3*match[y])//4) + [y] *3
    else:
        x = ''
        for num in '532':
            if num in A:
                x = num
                break
        if x:
            if N%5 == 0:
                ans = [x] * (N//5)
            elif N&5 == 1:
                flag = False
                for num in '96':
                    if num in A:
                        flag = True
                        ans = [x] * ((N - match[num])//5) + [num]
                        break
                if not flag:
                    ans = [x] * ((N - 3*match['8'])//5) + ['8'] * 3
            elif N%5 == 2:
                if '8' in A:
                    ans = [x] * ((N - match['8'])//5) + ['8']
                else:
                    for num in '96':
                        if num in A:
                            ans = [x] * ((N - 2*match[num])//5) + [num] * 2
                            break
            elif N%5 == 3:
                if '8' in A:
                    flag = False
                    for num in '96':
                        if num in A:
                            flag = True
                            ans = [x] * ((N - match[num] - match['8'])//5) + ['8',num]
                            break
                    if not flag:
                        ans = [x] * ((N - 4*match['8'])//5) + ['8'] * 4
            elif N%5 == 4:
                if '8' in A:
                    ans = [x] * ((N - 2*match['8'])//5) + ['8'] * 2
                else:
                    for num in '96':
                        if num in A:
                            ans = [x] * ((N - 4*match[num])//5) + [num] * 4
                            break

        else:
            y = ''
            for num in '96':
                if num in A:
                    y = num
                    break
            if y:
                if N%6 == 0:
                    ans = [y] * (N//6)
                else:
                    k = N%6
                    ans = [y] * ((N - k*match['8'])//6) + ['8'] * k
            else:
                ans = ['8'] * (N//7)
    ans.sort(reverse = True)
    print(''.join(ans))
if __name__ == '__main__':
    main()