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 = list(map(int,input().split()))
 
dp = [-1 for i in range(N+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(N-1):
    for s in A:
        if dp[i] == -1 and i!=0:
            continue
        if dp[i + l[s]] < dp[i]*10+s:
            dp[i + l[s]] = dp[i]*10+s
print(dp[N])

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

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

Solution (Python):
n, m = map(int, input().split())
*a, = map(int, input().split())
sorted_a = sorted(a, reverse=True)

needs = [9,2,5,5,4,5,6,3,7,6]
table = [-1] * (n+10)
table[0] = 0

for i in range(n):
    if table[i] != -1:
        for j in sorted_a:
            table[i + needs[j]] = max(table[i]*10 + j, table[i + needs[j]])

print(table[n])

Solution (Python):


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

    costs = [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 a in A:
            if i - costs[a] < 0:
                continue
            dp[i] = max(dp[i-costs[a]] + 1, dp[i])

    ans = ""
    remain = dp[N]
    match = N

    minCosts = 10
    for a in A:
        minCosts = min(minCosts, costs[a])

    while match > 0:
        for a in A:
            if match - costs[a] < 0 or 1<= match - costs[a] < minCosts:
                continue

            if dp[match-costs[a]] == remain-1:
                ans += str(a)
                match -= costs[a]
                remain -= 1
                break

    print(ans)


if __name__ == "__main__":
    resolve()

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] * (n + 10)
dp[0] = 0

for i in range(n):
    for ai in a:
        if dp[i] >= 0:
            dp[i + cost[ai]] = dp[i] + 1

ans = []
i = n
while dp[i] > 0:
    for ai in a:
        if dp[i - cost[ai]] == dp[i] - 1:
            ans.append(str(ai))
            i -= cost[ai]
            break

print(''.join(ans))

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right

import re







def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 


def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]



def main():
    H, M = l_inpl()
    A = l_inpl()
    d = {
        "1": 2,
        "2": 5,
        "3": 5,
        "4": 4,
        "5": 5,
        "6": 6,
        "7": 3,
        "8": 7,
        "9": 6
    }

    new_d = {}
    for Ai in A:
        new_d[Ai] = d[str(Ai)]

    dp = [-INF] * (H+1) 
    dp[0] = 0

    for i in range(1, H+1):
        tmp = []
        for k, v in new_d.items():
            if i-v < 0:
                tmp.append(-INF)
            else:
                tmp.append(dp[i-v]+1)
        dp[i] = max(tmp)

    s = sorted(new_d.items(), key=lambda x:-x[0])

    ans = ""
    remain = H

    while remain > 0:
        for k, v in s:
            if remain >= v and dp[remain-v] != -INF and dp[remain-v] == dp[remain] - 1: 
                ans += str(k)
                remain -= v
                break
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = {0: 0}
for i in range(1, N + 1):
    dp[i] = -float('inf')
    for j in range(8, -1, -1):
        if j + 1 in A and i - num[j] >= 0:
            dp[i] = max(dp[i], dp[i - num[j]] + 1)

ans = []
while N > 0:
    for j in range(8, -1, -1):
        if j + 1 in A and N - num[j] in dp and dp[N - num[j]] == dp[N] - 1:
            ans.append(j + 1)
            N -= num[j]
            break

print(*ans, sep='')

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

c = [0] * 8

mt = set()
for aa in a:
    if aa == 1:
        c[2] = 1
        mt.add(2)
    if aa == 2:
        c[5] = max(c[5], 2)
        mt.add(5)
    if aa == 3:
        c[5] = max(c[5], 3)
        mt.add(5)
    if aa == 4:
        c[4] = 4
        mt.add(4)
    if aa == 5:
        c[5] = max(c[5], 5)
        mt.add(5)
    if aa == 6:
        c[6] = max(c[6], 6)
        mt.add(6)
    if aa == 7:
        c[3] = 7
        mt.add(3)
    if aa == 8:
        c[7] = 8
        mt.add(7)
    if aa == 9:
        c[6] = max(c[6], 9)
        mt.add(6)
dp = [-1] * (n+1)
dp[0] = 0
for i in range(n+1):
    tmp = [dp[i]]
    for mtt in mt:
        if i-mtt>= 0 and dp[i-mtt] >= 0:
            tmp.append(dp[i-mtt]*10+c[mtt])
    dp[i] = max(tmp)
print(dp[n])

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
 
needs = [999,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 k in sorted(a, reverse=True): 
      matchs = needs[k] 
      dp[i+matchs] = max(dp[i+matchs], dp[i]*10+k) 
print(dp[n])

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

match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
dp = [[0] * M for _ in range(N + 1)]

for i in range(N + 1):
    for j in range(M):
        for k in range(M):
            if (i - match[A[k]] == 0) or \
                   (i - match[A[k]] > 0 and dp[i - match[A[k]]][j] != 0):
                dp[i][k] = max(dp[i][k], 
                               dp[i - match[A[k]]][j] * 10 + A[k])

print(max(dp[-1]))

Solution (Python):
def main():

    """ convenient functions
    
    
    
    
    
    """

    """convenient decorator
    
    
        
        
        
        
        
        
        
        
        
        
    """
    
    
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product 
    
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  
        b, e = 2, 0  
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict 
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
    from copy import deepcopy, copy 
    import operator
    from operator import itemgetter
    
    
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd 
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    
    
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) 
    def modinv(a, p = MOD):
        
        
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        
        
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    
        
        
    
        
        
        
        
        
    
        
        
        
        
    
        
        
    """

    
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    
    
    
    
    
    
    
    """

    if __name__ != '__main__':
        
        sys.stdin = open('sample.txt')
        
    
    

    N, M = R()
    A = R()
    A.sort()
    
    Dic = {1: 2, 2: 5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
    dp = [-INF] * (N+10)
    dp[0] = 0
    memo = [0] * (N+10)
    for i in A:
        stroke = Dic[i]
        for j in range(N):
            if dp[j] + 1 >= dp[j+stroke]:
                dp[j+stroke] = dp[j] + 1
                memo[j+stroke] = i
    ans = []
    k = N
    while k:
        tmp = memo[k]
        ans.append(tmp)
        k -= Dic[tmp]
    print(*sorted(ans,reverse=True),sep='')
    
    

    """memo: how to use defaultdict of list
    
    Dic = defaultdict(list)
    
    Dic[x].append(y)
    
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    
    >>> a = 5
    >>> bin_str_a = format(a, '
    >>> print(bin_str_a)
    0b0101 
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

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

costs = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]


dp = [[0, []] for _ in range(N + 1)]
for a in A:
	cost = costs[a]
	for n in range(N):
		if n != 0 and dp[n][0] == 0:
			continue
		ni = n + cost
		if N < ni:
			break
		np = [dp[n][0] + 1, sorted(dp[n][1] + [a], reverse=True)]
		if dp[ni] < np:
			dp[ni] = np

print(*sorted(dp[N][1], reverse=True), sep="")

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

needs = [10,2,5,5,4,5,6,3,7,6]
table = [-1] * (n + 10)
table[0] = 0

for i in range(n):
    if table[i] != -1:
        for number in sorted(a, reverse = True):
            matchs = needs[number]
            if table[i+matchs] == 0:
                table[i+matchs] = table[i] * 10 + number
            else:
                table[i+matchs] = max(table[i+matchs], table[i] * 10 + number)

print(table[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+10)
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+10)
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 sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

M = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = list(map(int,input().split()))
A = [[i,M[i]] for i in a]
A.sort(key = itemgetter(1))


dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(n):
    for j,k in A:
        if i + k < n+1:
            if dp[i] < 0:
                continue
            dp[i+k] = dp[i] + 1
A.sort(key = itemgetter(0),reverse = True)
ans = ''
k = n
while 1:
    for i,j in A:
        if k - j < 0:
            continue
        if dp[k-j] == dp[k]-1:
            ans += str(i)
            k -= j
            break
    else:
        break
print(ans)

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

Aset = {}
for a in A:
    c = cost[a]
    Aset[c] = max(Aset[c], a) if c in Aset else a
A = sorted([v for k,v in Aset.items()])

dp = [None]*(N+1)
dp[0] = (0,[0]*len(A))

for ia, a in enumerate(A):
    c = cost[a]
    for i in range(c, N+1):
        t = dp[i-c]
        if t and (dp[i]==None or t[0]+1>=dp[i][0]):
            dp[i] = (t[0]+1, t[1].copy())
            dp[i][1][ia] += 1
      	
l=[]
for i in range(len(A)):
    l += [A[len(A)-1-i]]*dp[N][1][len(A)-1-i]

print(*l, sep='')

Solution (Python):
def smax(s1, s2):
    if s1=="N":
        if s2[0]=="N":
            return "N"
        else:
            return s2
    if s2[0] == "N":
        return s1
    l1 = len(s1)
    l2 = len(s2)
    if l1 == l2:
        return max(s1, s2)
    if l1 > l2:
        return s1
    return s2

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

Solution (Python):
from collections import defaultdict

memo = []


def find(nowstr, rest):
    if rest < 0:
        return ""

    for i in costlist:
        if i < rest:
            find(nowstr+str(i), rest - i)
        elif i == rest:

            memo.append(nowstr+str(i))


def cost_to_num(c):
    if c == 2:
        return "1"
    if c == 3:
        return "7"
    if c == 4:
        return "4"

    if c == 5:
        if 2 in num_to_use:
            return "2"
        elif 3 in num_to_use:
            return "3"
        else:
            return "5"
    if c == 6:
        if 6 in num_to_use:
            return "6"
        else:
            return "9"
    if c == 7:
        return "8"


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

num_to_use = set(Alist)
"""
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 を 1 つ作るには、
2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 本のマッチ棒を使う。
"""
ref = [2, 5, 5, 4, 5, 6, 3, 7, 6]
if 9 in num_to_use:
    num_to_use.discard(6)
if 5 in num_to_use:
    num_to_use.discard(2)
    num_to_use.discard(3)
if 3 in num_to_use:
    num_to_use.discard(2)


costlist = [ref[i-1] for i in num_to_use]
costlist.sort()



minlength = N // costlist[0] - 5
if minlength < 0:
    minlength = 0
ans_tail = [cost_to_num(costlist[0])]*minlength

delta = N - minlength * costlist[0]

find("", delta)



ans_length = len(memo[0])
temp = 0
for i in memo:
    if len(i) < ans_length:
        continue

    numlist = [cost_to_num(int(j)) for j in i]+ans_tail
    
    numlist.sort(reverse=True)
    joined = "".join(numlist)
    
    if temp < int(joined):
        temp = int(joined)
ans_head = str(temp)


print(ans_head)

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [float("inf"), 2, 5, 5, 4, 5, 6, 3, 7, 6]
mincost = min(cost)

dp = [None] * (n + 1)
def dfs(at):
    if at < 0:
        return -1
    if at == 0:
        return 0
    if dp[at] is not None:
        return dp[at]
    r = max(dfs(at - cost[v]) * 10 + v for v in a)
    dp[at] = r
    return r


print(dfs(n))

Solution (Python):
N,M = map(int,input().split())
*A, = map(int,input().split())
B = sorted((([2,5,5,4,5,6,3,7,6][a-1],a) for a in A),key = lambda x:(x[0],-x[1]))
i = 1
while i<len(B):
    if B[i][0]==B[i-1][0]:
        B.pop(i)
    else:
        i+=1
i = [0]*(len(B)-1)
if len(B)==1:
    print(str(B[0][1])*(N//B[0][0]))
    exit()
ans = []
while i[-1]<B[0][0]:
    tmp = N - sum(j*b[0] for j,b in zip(i,B[1:]))
    if tmp>=0 and tmp%B[0][0] == 0:
        num = ""
        for k,n in sorted(zip([b for _,b in B],[tmp//B[0][0]]+i),key = lambda x:-x[0]):
            num += str(k)*n
        ans.append(int(num))
    i[0]+=1
    for j in range(len(i)-1):
        if i[j]==B[0][0]:
            i[j+1]+=1
            i[j]=0
print(max(ans))

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

matchuse = [5000000000000000, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [[]]
for i in range(0, 10):
	dp[0].append('')
made = []
for i in range(0, N+1):
	lst = []
	for j in range(0, M):
		lst.append(False)
	made.append(lst)
made[0][0] = True
for i in range(1, N+1):
	lst = []
	for j in range(0, M):
		next = ''
		if i - matchuse[A[j]] >= 0:
			index = i - matchuse[A[j]]
			for k in range(0, M):
				if made[index][k]:
					next = larger(next, dp[index][k]+str(A[j]))
		lst.append(next)
		if next != '':
			made[i][j] = True
	dp.append(lst)
ans = ''
for i in range(0, M):
	ans = larger(ans, dp[N][i])
print(ans)

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
match = []
for num in a:
    match.append(all_match[num-1])

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

for i in range(1,n+1):
    possible = []
    for honsu in match:
        if i >= honsu:
            possible.append(dp[i-honsu] + 1)
    if len(possible)>0:
        dp[i] = max(possible)

length = dp[n]
ans = 0
now = n
for i in range(length):
    for j in range(m):
        if now >= match[j]:
            if dp[now-match[j]] == dp[now]-1:
                ans += a[j]*10**(length-i-1)
                now -= match[j]
                break

print(ans)

Solution (Python):
from operator import itemgetter

inf = 10 ** 4

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

use = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]


use_num = {use[i]: i for i in range(1, 10) if i in a}
use_num = tuple(sorted(use_num.items()))



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


for j in range(2, n + 1):
    for use, number in use_num:
        k = j - use
        if k >= 0:
            dp[j] = max(dp[j], dp[k] + 1)


use_num = tuple(sorted(use_num, key=itemgetter(1), reverse=True))


rest = n
ans = ''
while rest > 0:
    for use, number in use_num:
        k = rest - use
        if (k >= 0) and (dp[k] == dp[rest] - 1):
            ans += str(number)
            rest -= use
            break
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)

inf = 10 ** 4


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    if memo[rest] is not None:
        return memo[rest]

    res = []
    for use, number in d.items():
        if rest - use >= 0 and dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))

    memo[rest] = res
    return res


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

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]


for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}


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


for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)



memo = [None] * (n + 1)

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Solution (Python):
n, m = [ int(v) for v in input().split() ]
num_list = [ int(v) for v in input().split() ]
match_table = [2,5,5,4,5,6,3,7,6]
match_table_2 = [ [] for i in range(8) ]
for i in num_list:
    match_table_2[match_table[i-1]].append(i)

match_table_2 = [ (max(match_table_2[i]), i) for i in range(8) if match_table_2[i] != [] ]
match_list, figure_list = zip(*match_table_2)
k = len(match_list)

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

for i in range(n+1):
    index_list = [ i - j for j in figure_list ]
    candidate_list = []
    for j in range(k):
        if index_list[j] > 0 and dp_list[index_list[j]] > 0:
            candidate_list.append(dp_list[index_list[j]] * 10 + match_list[j])
        elif index_list[j] == 0:
            candidate_list.append(match_list[j])
    if candidate_list != []:
        dp_list[i] = max(candidate_list)

print(dp_list[-1])

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

Solution (Python):
from math import isinf

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

m = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]






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

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

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if matches - m[a] < 0:
            continue
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

print(ans)

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

A.sort(reverse=True)

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

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

dp[0] = 0
for i in range(1, N+1) :
    maxDigit = -float('inf')
    for a in A :
        if i - match[a - 1] >= 0 :
            maxDigit = max(maxDigit, dp[i - match[a - 1]] + 1)
    dp[i] = maxDigit

maxDigit = dp[-1]

r = N

for _ in range(maxDigit) :
    for a in A :
        if r - match[a - 1] < 0 or r < 0 :
            continue
        if dp[r - match[a - 1]] == dp[r] - 1 :
            print(a, end='')
            r -= match[a - 1]
            break

print('')

Solution (Python):
a = [2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = sorted(set(list(map(int, input().split()))), reverse=True)
B = sorted([a[i-1] for i in A])

dp = [-1] * (N+1)
for b in B:
    if b < N+1:
        dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    if N-x >= 0:
        while dp[N-x] == digit-1:
            print(n, end='')
            N -= x
            digit -= 1
        if N == x:
            print(n, end='')
            N -= x

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

NUM = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-float('inf') for _ in range(N + 1)]
dp[0] = 0

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

dights = dp[N]
ans = ""
matchsticks = N
while(dights > 0):
    for a in A:
        if matchsticks - NUM[a - 1] >= 0 and dp[matchsticks - NUM[a - 1]] == dights - 1:
            ans += str(a)
            dights -= 1
            matchsticks -= NUM[a - 1]
            break

print(ans)

Solution (Python):
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
INF = float('inf')
for i in range(1, N+1):
    t = -INF
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5)
lst = [[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(reverse = True)


def num(k):
    return lst[k-1][1]


    


INF = 10 ** 5
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)






def check(A):
    if N - num(A) < 0:
        return False
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False


while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            
print ()