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
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

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

b = list(map(int,input().split()))
honsuu = [-1,2,5,5,4,5,6,3,7,6]
enabled = [False] * 10
for bb in b:
    enabled[bb] = True
if (enabled[6] & enabled[9]):
     enabled[6] = False;
if (enabled[5] & (enabled[2] | enabled[3])):
     enabled[2] = enabled[3] = False;
if (enabled[2] & enabled[3]):
     enabled[2] = False


def printf(str):
    l = list(str)
    l = sorted(l, reverse=True)
    print("".join(l))

a = []
for i in range(10):
    if (enabled[i]):
        a.append(i)

if enabled[1]:
    if n % 2 == 1:
        if enabled[7]:
            res = "7" + ((n - 3) // 2) * "1"
        elif enabled[5]:
            res = "5" + ((n - 5) // 2) * "1"
        elif enabled[3]:
            res = "3" + ((n - 5) // 2) * "1"
        elif enabled[2]:
            res = "2" + ((n - 5) // 2) * "1"
        else:
            res = "8" + ((n - 7) // 2) * "1"
        printf(res)
    else:
        printf("1" * (n // 2))
    exit()

if enabled[7]:
    if n % 3 == 1:
        if enabled[4]:
            res = "7" * ((n - 4) // 3) + "4"
        elif enabled[8]:
            res = "8" + "7" * ((n - 7) // 3)
        elif enabled[5]:
            res = "7" * ((n - 10) // 3) + "55"
        elif enabled[3]:
            res = "7" * ((n - 10) // 3) + "33"
        elif enabled[2]:
            res = "7" * ((n - 10) // 3) + "22"
        printf(res)
    elif n % 3 == 0:
        printf("7" * (n // 3))
    else:
        if enabled[5]:
            res = "7" * ((n - 5) // 3) + "5"
        elif enabled[3]:
            res = "7" * ((n - 5) // 3) + "3"
        elif enabled[2]:
            res = "7" * ((n - 5) // 3) + "2"
        elif enabled[4]:
            res = "7" * ((n - 8) // 3) + "44"
        elif enabled[8]:
            res = "88" + "7" * ((n - 14) // 3)
        printf(res)
    exit()

if enabled[4]:
    if n % 4 == 0:
        printf("4" * (n // 4))
    elif n % 4 == 1:
        if enabled[5]:
            res = "5" + "4" * ((n - 5) // 4)
        elif enabled[3]:
            res = "4" * ((n - 5) // 4) + "3"
        elif enabled[2]:
            res = "4" * ((n - 5) // 4) + "2"
        elif enabled[8]:
            if enabled[9]:
                res = "98" + ((n - 13) // 4) * "4"
            elif enabled[6]:
                res = "86" + ((n - 13) // 4) * "4"
            else:
                res = "888" + ((n - 21) // 4) * "4"
        printf(res)
    elif n % 4 == 2:
        if enabled[9]:
            res = "9" + "4" * ((n - 6) // 4)
        elif enabled[6]:
            res = "6" + "4" * ((n - 6) // 4)
        elif enabled[5]:
            res = "55" + "4" * ((n - 10) // 4)
        elif enabled[3]:
            res = "4" * ((n - 10) // 4) + "33"
        elif enabled[2]:
            res = "4" * ((n - 10) // 4) + "22"
        elif enabled[8]:
            res = "88" + ((n - 14) // 4) * "4"
        printf(res)
    else:
        if enabled[9]:
            if enabled[5]:
                res = "95" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "9" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "9" + "4" * ((n - 11) // 4) + "2"
        elif enabled[8]:
            res = "8" + "4" * ((n - 7) // 4)
        elif enabled[6]:
            if enabled[5]:
                res = "65" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "6" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "6" + "4" * ((n - 11) // 4) + "2"
        elif enabled[5]:
            res = "555" + "4" * ((n - 15) // 4)
        elif enabled[3]:
            res = "4" * ((n - 15) // 4) + "333"
        else:
            res = "4" * ((n - 15) // 4) + "222"
        printf(res)
    exit()

for i in [5, 3, 2]:
    c = str(i)
    if enabled[i]:
        if n % 5 == 0:
            printf(c * (n // 5))
        elif n % 5 == 1:
            if enabled[9]:
                res = "9" + c * ((n - 6) // 5)
            elif enabled[6]:
                res = "6" + c * ((n - 6) // 5)
            else:
                res = "888" + c * ((n - 21) // 5)
            printf(res)
        elif n % 5 == 2:
            if enabled[9]:
                res = "99" + c * ((n - 12) // 5)
            elif enabled[8]:
                res = "8" + c * ((n - 7) // 5)
            else:
                res = "66" + c * ((n - 12) // 5)
            printf(res)
        elif n % 5 == 3:
            if enabled[9]:
                res = "999" + c * ((n - 18) // 5)
            elif enabled[6]:
                if enabled[8]:
                    res = "86" + c * ((n - 13) // 5)
                else:
                    res = "666" + c * ((n - 18) // 5)
            else:
                res = "8888" + c * ((n - 28) // 5)
            printf(res)
        else:
            if enabled[9]:
                res = "9999" + c * ((n - 24) // 5)
            elif enabled[8]:
                res = "88" + c * ((n - 14) // 5)
            else:
                res = "6666" + c * ((n - 24) // 5)
            printf(res)
        exit()

if enabled[9]:
    c = "9"
    if n % 6 == 0:
        printf(c * (n // 6))
    elif n % 6 == 1:
        printf(c * ((n - 7) // 6) + "8")
    elif n % 6 == 2:
        printf(c * ((n - 14) // 6) + "88")
    elif n % 6 == 3:
        printf(c * ((n - 21) // 6) + "888")
    elif n % 6 == 4:
        printf(c * ((n - 28) // 6) + "8888")
    else:
        printf(c * ((n - 35) // 6) + "88888")
    exit()

if enabled[6]:
    c = "6"
    if n % 6 == 0:
        printf(c * (n // 6))
    elif n % 6 == 1:
        printf("8" + c * ((n - 7) // 6))
    elif n % 6 == 2:
        printf("88" + c * ((n - 14) // 6))
    elif n % 6 == 3:
        printf("888" + c * ((n - 21) // 6))
    elif n % 6 == 4:
        printf("8888" + c * ((n - 28) // 6))
    else:
        printf("88888" + c * ((n - 35) // 6))
    exit()

printf("8" * (n // 7))

Solution (Python):
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]



best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

print(ans)

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

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

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


for i in range(m):
    if cost[a[i]] <= n:
        dp[cost[a[i]]]= [a[i]]


for i in range(0,n+1):
    for k in range(m):
        if i > cost[a[k]]:
            
            tmp = copy.copy(dp[i-cost[a[k]]])
            tmp.append(a[k])
            tmp.sort(reverse = True)
            
            if len(tmp) > len(dp[i]) and len(tmp) != 1:
                dp[i] = tmp
            elif len(tmp) == len(dp[i]) and len(tmp) != 1:
                big = 0

                for s in range(len(tmp)):
                    if tmp[s] > dp[i][s]:
                        big = 1
                        break
                    elif tmp[s] < dp[i][s]:
                        big = 0
                        break
                if(big):
                    dp[i] = tmp
            

ans = ""
for cha in dp[n]:
    ans = ans + str(cha)
print(ans)

Solution (Python):
import copy

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

dp = [[0 for _ in range(10)] for i in range(N+10)]

A = sorted(A, reverse=True)

for num in A:
    c = cost[num]
    if dp[c][0] == 0:
        dp[c][0] = 1
        dp[c][num] = 1

for i in range(1, N+1):
    for num in A:
        c = cost[num]
        prev = copy.deepcopy(dp[i])
        if prev[0] != 0:
            if dp[i + c][0] > dp[i][0] + 1:
                continue
            elif dp[i + c][0] == dp[i][0] + 1:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                for number in range(9, 0, -1):
                    if dp[i + c][number] < nxt[number]:
                        dp[i + c] = copy.deepcopy(nxt)
                        break
                    if dp[i + c][number] > nxt[number]:
                        break
            else:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                dp[i + c] = copy.deepcopy(nxt)


ans = ""
for number in range(9, 0, -1):
    for _ in range(dp[N][number]):
        ans = ans + str(number)

print(ans)

Solution (Python):
import copy

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

dp = [[0 for _ in range(10)] for i in range(N+10)]

A = sorted(A, reverse=True)

for num in A:
    c = cost[num]
    if dp[c][0] == 0:
        dp[c][0] = 1
        dp[c][num] = 1

for i in range(1, N+1):
    for num in A:
        c = cost[num]
        prev = copy.deepcopy(dp[i])
        if prev[0] != 0:
            if dp[i + c][0] > dp[i][0] + 1:
                continue
            elif dp[i + c][0] == dp[i][0] + 1:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                for number in range(9, 0, -1):
                    if dp[i + c][number] < nxt[number]:
                        dp[i + c] = copy.deepcopy(nxt)
                        break
                    if dp[i + c][number] > nxt[number]:
                        break
            else:
                nxt = prev
                nxt[num] += 1
                nxt[0] += 1
                dp[i + c] = copy.deepcopy(nxt)


ans = ""
for number in range(9, 0, -1):
    for _ in range(dp[N][number]):
        ans = ans + str(number)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
costs = [2,5,5,4,5,6,3,7,6] 
costmap = {}
for num in numbers:
  cost = costs[num-1]
  if cost in costmap and num < costmap[cost]:
    continue
  costmap[cost] = num

from functools import lru_cache
@lru_cache(None)
def recursive(remain=N):
  maxval = costmap[remain] if remain in costmap else 0
  for cost, num in costmap.items():
    if remain > cost:
      val = recursive(remain-cost)
      if val == 0:
        continue
      val = val * 10 + num
      if val > maxval:
        maxval = val
  return maxval
 
print(recursive(N))

Solution (Python):

def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7
    if x == 9:
        return 6
n,m = map(int,input().split())
a = list(map(int,input().split()))
if 2 in a and 3 in a:
    a.remove(2)
    m -=1
if 2 in a and 5 in a:
    a.remove(2)
    m -=1
if 3 in a and 5 in a:
    a.remove(3)
    m -=1
if 6 in a and 9 in a:
    a.remove(6)
    m -=1
for w in range(1,10):
    if n < f(w) and w in a:
        a.remove(w)
        m -=1
a.sort()
m = len(a)

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


def g(k):
    cand = [0]*(m+1)
    for i in range(m):
        if k - f(a[i])>=0:
            if cand[0] <= dp[k-f(a[i])][0]+1 and dp[k-f(a[i])][0] != 0:
                for r in range(m+1):
                    cand[r] = dp[k-f(a[i])][r]
                cand[0] += 1
                cand[i+1] += 1
    if sum(cand) != 0:
        dp[k] = cand
for i in range(m):
    if f(a[i]) <= n:
        dp[f(a[i])][0] = 1
        dp[f(a[i])][i+1] = 1

for j in range(1,n+1):
    g(j)

ass = ''

for i in range(m):
    for k in range(dp[n][m-i]):
        ass += str(a[m-i-1])
print(ass)

Solution (Python):
import math
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
mp = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
dp = [''] * (N+1)
for i in range(1, N+1):
    cand = []
    for x in A:
        if i - mp[x] < 0:
            continue
        if dp[i-mp[x]] == '' and mp[x] != i:
            continue
        if dp[i-mp[x]] == '':
            cand.append(x)
        else:
            before = dp[i - mp[x]]
            pre = (int(math.log10(before)) + 1) * 10 * x + before
            suf = before * 10 + x
            cand.append(max(pre, suf))
    if cand:
        dp[i] = max(cand)
    else:
        dp[i] = ''
print(dp[N])

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

d = [2,5,5,4,5,6,3,7,6]
a.sort()
dic = {}
for ai in a:
    dic[d[ai-1]] = ai

dp = [""] + ["0"] * n
for i in range(n + 1):
    for j, k in dic.items():
        if i - j >= 0 and dp[i - j] != '0':
            temp = str(k) + dp[i - j]
            if len(temp) >= len(dp[i]) and temp > dp[i]:
                dp[i] = temp
                
print(dp[-1])

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

Solution (Python):
from copy import deepcopy
NUM = [10000, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6]
n, m = map(int, input().split())
aa = list(map(int, input().split()))

dp = [[-1 for j in range(9)] for i in range(n + 1)]
for j in range(9):
    dp[0][j] = 0
for i in range(1, n + 1):
    for a in aa:
        if i - NUM[a] >= 0 and dp[i - NUM[a]][0] != -1:
            tmp = deepcopy(dp[i - NUM[a]])
            tmp[9 - a] += 1
            if sum(tmp) > sum(dp[i]) or (sum(tmp) == sum(dp[i]) and tmp > dp[i]):
                dp[i] = tmp
ans = ""
for j in range(9):
    for k in range(dp[n][j]):
        ans += str(9 - j)
print(ans)

Solution (Python):

math_inf = float('inf')  

def solve(n, m, a):
    cost = [ math_inf, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
    dp = [ None ] * (n + 1)
    dp[0] = 0
    for i in range(1, len(dp)):
        dp[i] = max([ dp[i - cost[a_i]] * 10 + a_i for a_i in a if cost[a_i] <= i ] + [ - math_inf ])
    return str(dp[n])


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

Solution (Python):
import sys
sys.setrecursionlimit(150000)


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

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

memo = [ "-" for _ in range(N + 1)]

def find(N):
    global memo
    if memo[N] != "-":
        return memo[N]

    mval = ""
    val = ""
    for a in A:
        if d[a - 1] < N:
            val = find(N - d[a - 1])
            if val == "":
                continue
            val = val + str(a)
        elif d[a - 1] == N:
            val = str(a)
        else:
            continue

        if len(mval) < len(val) or (len(mval) == len(val) and mval < val):
            mval = val
    memo[N] = mval
    return memo[N]

m = find(N)
print(m)

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

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

for i in range(2, N+1):
    x = -1
    opt = -1
    for a in A:
        c = C[a]
        if i >= c and (dp2[i - c] > opt or (dp2[i - c] == opt and a > x)):
            x = a
            opt = dp2[i - c]
    if x == -1:
        continue
    dp2[i] = dp2[i - C[x]] + 1
    c = C[x]
    for a in A:
        if x == a:
            dp[i][a] = dp[i - c][a] + 1
        else:
            dp[i][a] = dp[i - c][a]

ans = ''.join(str(a) * dp[N][a] for a in sorted(A, reverse=True))
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):

from collections import defaultdict
import math
import bisect
import random
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return list(input())
def IIR(n): return [II() 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)]
mod = 1000000007


"""
a,b = LI()
if b % a == 0:
    print(a+b)
else:
    print(b-a)
"""


"""
n,m = LI()
lis = [0 for i in range(m)]
for i in range(n):
    k = LI()
    for j in k[1:]:
        lis[j-1] += 1
ans = 0
for i in lis:
    if i == n:ans += 1
print(ans)
"""


"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = II()
a = LI()
ans = a[0]
for i in range(1,n):
    ans = gcd(ans,a[i])
print(ans)
"""


n,m = LI()
a = LI()
f = [0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    a[i] = [a[i],f[a[i]]]
a.sort(key = lambda x:x[1])
dp = [[] for i in range(n+10)]
for i in a:
    dp[i[1]] = [i[0]]
for i in range(n+1):
    for j in a:
        if i-j[1] >= 0 and len(dp[i-j[1]]) > 0:
            if len(dp[i]) < len(dp[i-j[1]])+1:
                dp[i] = dp[i-j[1]]+[j[0]]
                dp[i].sort()
                dp[i] = dp[i][::-1]
            else:
                if len(dp[i]) == len(dp[i-j[1]])+1:
                    d = sorted(dp[i-j[1]]+[j[0]])
                    d = d[::-1]
                    k = [dp[i],d]
                    k.sort()
                    if k[1] == d:
                        dp[i] = d
ans = 0
k = 1
l = len(dp[n])
for i in range(l):
    ans += k*dp[n][l-i-1]
    k *= 10
print(ans)

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


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

maxnum = [None] * (N + 1 + 10)
maxnum[0] = (0, 0)

if 9 in A and 6 in A:
    A.remove(6)

if 5 in A and 2 in A:
    A.remove(2)
if 5 in A and 3 in A:
    A.remove(3)

if 3 in A and 2 in A:
    A.remove(2)

if 1 in A and 4 in A:
    A.remove(4)
if 1 in A and 6 in A:
    A.remove(6)
if 1 in A and 9 in A:
    A.remove(9)

if 7 in A and 6 in A:
    A.remove(6)
if 7 in A and 9 in A:
    A.remove(9)



i = 0
while i < N:
    n = maxnum[i]
    if not n is None:
        for a in A:
            m = (n[0] + 1, 10 ** n[0] * a + n[1])
            j = i + SEGTBL[a]
            prem = maxnum[j]
            maxnum[j] = m if prem is None else max(prem, m)
    i += 1

print(maxnum[N][1])

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]
ab = {}
for i in a:
    ab[i] = b[i]
dp = [0]*(n+10)
dp[0] = ""
for i in range(n+1):
    if dp[i] == 0:
        continue
    for j in ab.keys():
        if dp[i] == "":
            dp[i+ab[j]] = str(max(int(dp[i+ab[j]]),j))
        else:
            if dp[i][0]> str(j):
                next0 = dp[i]+str(j)
            else:
                next0 = str(j)+dp[i]
            if dp[i+ab[j]] == 0:
                dp[i+ab[j]] = next0
                continue
            if len(next0) > len(dp[i+ab[j]]):
                dp[i+ab[j]] = next0
            elif len(next0) < len(dp[i+ab[j]]):
                continue
            else:
                for k in range(len(next0)):
                    if next0[k]> dp[i+ab[j]][k]:
                        dp[i+ab[j]] = next0
                        break
                    elif next0[k]< dp[i+ab[j]][k]:
                        break
                else:
                    dp[i+ab[j]] = next0

print(dp[n])

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

A.sort()
DP = [0] * (n+1)

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

print(DP[n])

Solution (Python):
from fractions import gcd

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

A = set(map(int,input().split()))
D = [None,2,5,5,4,5,6,3,7,6]

B = set(D[i] for i in range(1,10) if i in A)


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

for i in range(N+1):
  for d in B:
    if i-d >= 0 and dp[i-d] >= 0:
      dp[i] = max(dp[i],1 + dp[i-d])


res = []

digits = dp[N]
C = sorted(((i,D[i]) for i in range(1,10) if i in A), reverse=True)

i = N

for remaining in reversed(range(digits)):
  for v,d in C:
    if i-d >= 0 and dp[i-d] == remaining:
      res.append(v)
      i -= d
      break

print(*res,sep='')

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):

def main():
    
    N,M = list(map(int,input().split()))
    a = list(map(int,input().split()))
    c = [2,5,5,4,5,6,3,7,6]
    dp = [int(-1e7) for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        for j in a:
            if i-c[j-1]>=0:
                dp[i] = max(dp[i],dp[i-c[j-1]]+1)
    ans = ""
    now = N
    for _ in range(dp[N]):
        ag = -1
        ma = -1
        for j in a:
            if now - c[j-1] < 0:
                continue
            if dp[now]!=dp[now-c[j-1]]+1:
                continue
            if j > ma:
                ma = j
        now -= c[ma-1]
        ans += str(ma)
    print(ans)

if __name__=='__main__':
    main()

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]
f = [-1]*10010
f[0] = 0
for i in range(1, n+1):
	for x in a:
		if i-c[x] >= 0:
			f[i] = max(f[i], f[i-c[x]]*10+x)
print(f[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
readline = sys.stdin.readline
writelines = sys.stdout.writelines
write = sys.stdout.write

N, M = map(int, readline().split())
*A, = map(int, readline().split())

A.sort(reverse=1)
CS = [0,2,5,5,4,5,6,3,7,6]

INV = (None, 0)
EMP = ([], 0)

memo = [[-1]*(N+1) for i in range(M+1)]
mM = memo[M]
mM[0] = EMP
for i in range(1, N+1):
    mM[i] = INV
def dfs(rest, i):
    mi = memo[i]
    if mi[rest] != -1:
        return mi[rest]
    v = A[i]; cost = CS[v]
    r = None
    cnt = 0
    k = 0
    kc = 0
    for k in range((rest // cost) + 1):
        r0, c0 = dfs(rest-k*cost, i+1)
        if r0 is not None:
            cnt0 = k + c0
            if r is None or cnt <= cnt0:
                r = r0
                cnt = cnt0
                kc = k
    if r is None:
        mi[rest] = INV
        return INV
    mi[rest] = res = [kc] + r, cnt
    return res
res, _ = dfs(N, 0)
ans = []
for i in range(M):
    ans.append(str(A[i]) * res[i])
writelines(ans)
write("\n")

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

n, m = map(int, input().split())
alist = list(map(int, input().split()))
alist.sort(reverse=True)

dp = [-1 for _ in range(n + 1)]
dp[0] = 0
for a in alist:
    match = matches[a]
    for i in range(n - match + 1):
        if dp[i] == -1: continue
        dp[i + match] = max(dp[i + match], dp[i] * 10 + a)

print(dp[-1])

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

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

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

ans = ""
p = N
while p>0:
  ans += str(T[p][1])
  p -= C[T[p][1]]
print ans

Solution (Python):
N, m = map(int, raw_input().split())
a = map(int, raw_input().split())
C = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

C = [C[A] for A in a]

dp = [-float('inf')] * (N + 1)
dp[0] = 0
for i in range(1, N + 1):
    for j in range(len(C)):
        if C[j] <= i:
            dp[i] = max(dp[i], dp[i - C[j]] * 10 + a[j])

print dp[N]