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

comall = [-1,2,5,5,4,5,6,3,7,6]
com = [ (i,comall[i]) for i in li ]
com.sort( key=lambda x:-x[0])

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

for i in range(N+1):
  for j,c in com:
    if (c==-1):
      continue
    if ( i-c < 0 ):
      continue
    if ( dp[i-c] == -1 ):
      continue
    dp[i] = max( dp[i] , dp[i-c] + 1 )

match = N
keta = dp[N]
st = ""


for i in range( 10000 ):
  for j,c in com:
    if (match-c<0):
      continue
    if (keta-1==dp[match-c]):
      keta-=1
      match-=c
      st+=str(j)
      break
  if (match==0):
    break
print ( st )

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}
memo=[0]*(n+1)
memo[0]=0
memo[1]=-10**10
for i in range(2, n+1):
    res=-10**10
    for ai in a:
        if d[ai]>i:
            continue
        res=max(res, ai+memo[i-d[ai]]*10)
    memo[i]=res
print(memo[n])

Solution (Python):
n, _ = map(int, input().split())
L = 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 L:
        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())
As = list(map(str,input().split()))
match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}
 



 
 
ws = {} 
for a in As:
    w = match[a] 
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())
 
dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):
    dp[i] = "-1"
 
for i in range(N+1):
    
    for a,k in zip(ns,ks):
        if i+k <= N:
            if dp[i] == "-1":
                dp[i+k] = str(max(int(dp[i]+a),int(dp[i+k])))
            elif dp[i] == "0":
                dp[i+k] = str(max(int(a),int(dp[i+k])))
            elif len(dp[i+k]) < len(dp[i])+1:
                    dp[i+k] = dp[i]+a
            elif len(dp[i+k]) == len(dp[i])+1:
                dp[i+k] = max(dp[i+k],dp[i]+a)
            
            

        else:
            continue
print(dp[N])

Solution (Python):

 
N,M = map(int,input().split())
As = list(map(str,input().split()))
match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}
 



 
 
ws = {} 
for a in As:
    w = match[a] 
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())
 
dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):
    dp[i] = "-1"
 
for i in range(N+1):
    
    for a,k in zip(ns,ks):
        if i+k <= N:
            if dp[i] == "-1":
                dp[i+k] = str(max(int(dp[i]+a),int(dp[i+k])))
            elif dp[i] == "0":
                dp[i+k] = str(max(int(a),int(dp[i+k])))
            elif len(dp[i+k]) < len(dp[i])+1:
                    dp[i+k] = dp[i]+a
            elif len(dp[i+k]) == len(dp[i])+1:
                dp[i+k] = max(dp[i+k],dp[i]+a)
            else:
                dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))

        else:
            continue
print(dp[N])

Solution (Python):
N, M = [int(a) for a in input().split(" ")]
ctab = {"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
A = sorted([(a, ctab[a]) for a in input().split(" ")], key=lambda t:t[0])
prev, curr = ([""]*(N+1), [""]*(N+1))

def maxs(s1, s2):
    return max(s1, s2, key=lambda s:len(s)) if len(s1)!=len(s2) else max(s1,s2)

char, cost = A[0]
for i in range(1, N+1):
    d, r = divmod(i, cost)
    prev[i] = char*d if r==0 else None
for char, cost in A[1:]:
    for i in range(1, N+1):
        if i-cost >= 0 and curr[i-cost] is not None:
            tmp = char+curr[i-cost]
            curr[i] = maxs(tmp, prev[i]) if prev[i] else tmp
        else:
            curr[i] = prev[i]
    curr, prev = prev, curr
print(prev[-1])

Solution (Python):
from functools import lru_cache

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

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


@lru_cache(None)
def f(n):
    if n == 0:
        return 0
    values = [f(n-costs[a]) * 10 + a for a in A if n >= costs[a]]
    if len(values) > 0:
        return max(values)
    return -1


[f(i) for i in range(N)]
print(f(N))

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    cs = [0, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 ]
    dp = [-float('inf')] * (N + 1)

    dp[0] = 0
    for i in range(1, len(dp)):
        for a in A:
            c = cs[a]
            if 0 <= i - c:
                dp[i] = max(dp[i], dp[i-c] + 1)
    i = N
    ret = 0
    while 0 < dp[i]:
        for a in A:
            c = cs[a]
            if (0 <= i - c) and (dp[i] == (dp[i - c] + 1)):
                i -= c
                ret = 10 * ret + a
                break
    return ret


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

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]
for i in range(9):
    if i+1 not in a:
        num[i]=0
dp=[[0]*10 for i in range(n+1)]
from copy import deepcopy
for i in range(2,n+1):
    for j in range(9):
        if num[j]>0 and num[j]<=i and dp[i][0]<=dp[i-num[j]][0]+1:
            if dp[i-num[j]][0]==0 and i-num[j]!=0:
                continue
            else:
                dp[i]=deepcopy(dp[i-num[j]])
                dp[i][0]+=1
                dp[i][j+1]+=1
ans=dp[n]
for i in range(9,0,-1):
    while ans[i]!=0:
        print(i,end='')
        ans[i]-=1
print()

Solution (Python):

import sys


def solve(N: int, M: int, A: "List[int]"):
    cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort()
    D = {cost[i-1]: i for i in A}
    cost = sorted(D.keys())
    dp = [-1] * (N+1)
    dp[0] = 0
    for i in range(N+1):
        if dp[i] == -1:
            continue
        for c, d in D.items():
            if i + c <= N:
                dp[i+c] = max(dp[i+c], dp[i] * 10 + d)
    print(dp[N])
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
import numpy as np
gcd = lambda a:functools.reduce(fractions.gcd,a) 
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) 
lcm = lambda a:functools.reduce(lcm_base,a,1) 

init_dp = lambda v,n:[v]*(n)

import math

ceil = lambda a:math.ceil(a) 
floor = lambda a:math.floor(a) 

def solution():
    N,M = input_ints()
    As = input_ints_list()
    w = [0,2,5,5,4,5,6,3,7,6]

    dp = init_dp(-1,N+1)
    dp[0] = 0
    for i in range(N+1):
        for v in As:
            if i+w[v] < N+1:
                dp[i+w[v]] = max(dp[i+w[v]],dp[i]*10+v)
    print(dp[N])
    
if __name__ == '__main__':
    solution()

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

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

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

ans = ''
num, digit = N, dp[N]
while num > 0:
    for a in A:
        i = num - f[a]
        if i >= 0 and dp[i] == digit - 1:
            ans += str(a)
            num -= f[a]
            digit -= 1
            break
print(ans)

Solution (Python):
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,f:[f() for _ in range(n)]

import functools,fractions
import numpy as np
gcd = lambda a:functools.reduce(fractions.gcd,a) 
lcm_base = lambda a,b:(a*b)//fractions.gcd(a,b) 
lcm = lambda a:functools.reduce(lcm_base,a,1) 

init_dp = lambda v,n:[v]*(n+1)

import math

ceil = lambda a:math.ceil(a) 
floor = lambda a:math.floor(a) 

def solution():
    N,M = input_ints()
    As = input_ints_list()
    w = [0,2,5,5,4,5,6,3,7,6]

    dp = init_dp(-1,N)
    dp[0] = 0
    for i in range(N+1):
        for v in As:
            if i+w[v] < N+1:
                dp[i+w[v]] = max(dp[i+w[v]],dp[i]*10+v)
    print(dp[N])




if __name__ == '__main__':
    solution()

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

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


dp = [-1*inf]*(N+1)
dp[0] = 0
for i in range(1,N+1):
  dp_new = 0
  for j in A:
    if i - number[j] >= 0:
      if dp[i-number[j]] +1 > dp_new:
        dp[i] = dp[i-number[j]] +1
        dp_new = dp[i]

A.sort(reverse=True)
ans = ""
while N > 0:
  for j in A:
    if N - number[j] >= 0:
      if dp[N] == dp[N-number[j]] + 1:
        ans += str(j)
        N -= number[j]
        break

print(int(ans))

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

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

dp=[ None for i in range(N+1) ] 
dp[0]=""


for i in range(N):
	if dp[i] is not None:
		for a in A:
			match_cnt=match[a]
			if 0<=i+match_cnt<=N:
				if dp[i+match_cnt] is None:
					dp[i+match_cnt]=dp[i]+str(a)
				else:
					if len(dp[i+match_cnt]) < len( dp[i]+str(a) ):
						dp[i+match_cnt]=dp[i]+str(a)
					else:
						dp[i+match_cnt]=max( dp[i+match_cnt], dp[i]+str(a) )
									

print dp[N]

Solution (Python):
T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]
 
N,M=map(int, raw_input().split())
A=map(int, raw_input().split())
 
 
P=[]
for i in A:
	P.append(T[i-1])
 
 
dp=[ None for i in range(N+1) ]
dp[0]=""
 
 
for i in range(N):
	
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:
 
				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )
 
 
print dp[N]

Solution (Python):
nm = input().split()
n = int(nm[0])
m = int(nm[1])
alist = set([int(i) for i in input().split()])

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


def print_count(num_count_list):
    to_print = ''
    num_count_list.sort(reverse=True)
    for num, count in num_count_list:
        to_print += str(num) * count
    print(to_print)


def safe_max(nset):
    try:
        return max(nset)
    except:
        return -1


if piece_num[2] & alist:
    max_2 = max(piece_num[2] & alist)
    if n & 1 == 0:
        print(str(max_2) * (n // 2))
    else:
        if piece_num[3] & alist:
            print_count([(max(piece_num[3] & alist), 1), (max_2, max(0, n // 2 - 1))])
        elif piece_num[5] & alist:
            print_count([(max(piece_num[5] & alist), 1), (max_2, max(0, n // 2 - 2))])
        elif piece_num[7] & alist:
            print_count([(max(piece_num[7] & alist), 1), (max_2, max(0, n // 2 - 3))])

elif piece_num[3] & alist:
    max_3 = max(piece_num[3] & alist)
    if n % 3 == 0:
        print(str(max_3) * (n // 3))
    elif n % 3 == 1:
        if piece_num[4] & alist:
            print_count([(max(piece_num[4] & alist), 1), (max_3, max(0, n // 3 - 1))])
        elif piece_num[7] & alist:
            print_count([(max(piece_num[7] & alist), 1), (max_3, max(0, n // 3 - 2))])
        elif piece_num[5] & alist:
            print_count([(max(piece_num[5] & alist), 2), (max_3, max(0, n // 3 - 3))])
    elif n % 3 == 2:
        if piece_num[5] & alist:
            max_5 = max(piece_num[5] & alist)
            print_count([(max_5, 1), (max_3, max(0, n // 3 - 1))])
        elif piece_num[4] & alist:
            max_4 = max(piece_num[4] & alist)
            print_count([(max_4, 2), (max_3, max(0, n // 3 - 2))])
        else:
            print_count([(max(piece_num[7] & alist), 2), (max_3, max(0, n // 3 - 4))])

elif piece_num[4] & alist:
    max_4 = max(piece_num[4] & alist)
    if n % 4 == 0:
        print(str(max_4) * (n // 4))
    elif n % 4 == 1:
        if piece_num[5] & alist:
            print_count([(max(piece_num[5] & alist), 1), (max_4, max(0, n // 4 - 1))])
        elif (piece_num[6] & alist) and (piece_num[7] & alist):
            max_6 = max(piece_num[6] & alist)
            max_7 = max(piece_num[7] & alist)
            print_count([(max_6, 1), (max_7, 1), (max_4, max(0, n // 4 - 3))])
        elif piece_num[7] & alist:
            max_7 = max(piece_num[7] & alist)
            print_count([(max_7, 3), (max_4, max(0, n // 4 - 5))])
    elif n % 4 == 2:
        if (piece_num[5] & alist) and (piece_num[6] & alist):
            max_5 = max(piece_num[5] & alist)
            max_6 = max(piece_num[6] & alist)
            if max_5 < max_6:
                print_count([(max_6, 1), (max_4, max(0, n // 4 - 1))])
            else:
                print_count([(max_5, 2), (max_4, max(0, n // 4 - 2))])
        elif piece_num[5] & alist:
            max_5 = max(piece_num[5] & alist)
            print_count([(max_5, 2), (max_4, max(0, n // 4 - 2))])
        elif piece_num[6] & alist:
            max_6 = max(piece_num[6] & alist)
            print_count([(max_6, 1), (max_4, max(0, n // 4 - 1))])
        else:
            max_7 = max(piece_num[7] & alist)
            print_count([(max_7, 2), (max_4, max(0, n // 4 - 3))])
    elif n % 4 == 3:
        max_5 = safe_max(piece_num[5] & alist)
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_5, max_6, max_7):
            print_count([(max_7, 1), (max_4, max(0, n // 4 - 1))])
        elif max_5 == max(max_5, max_6, max_7):
            print_count([(max_5, 3), (max_4, max(0, n // 4 - 3))])
        else:
            if piece_num[5] & alist:
                print_count([(max_6, 1), (max_5, 1), (max_4, max(0, n // 4 - 2))])
            else:
                print_count([(max_7, 1), (max_4, max(0, n // 4 - 1))])

elif piece_num[5] & alist:
    max_5 = max(piece_num[5] & alist)
    if n % 5 == 0:
        print(str(max_5) * (n // 5))
    elif n % 5 == 1:
        if piece_num[6] & alist:
            max_6 = safe_max(piece_num[6] & alist)
            print_count([(max_6, 1), (max_5, max(0, n // 5 - 1))])
        else:
            max_7 = safe_max(piece_num[7] & alist)
            print_count([(max_7, 3), (max_5, max(0, n // 5 - 4))])
    elif n % 5 == 2:
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_6, max_7):
            print_count([(max_7, 1), (max_5, max(0, n // 5 - 1))])
        else:
            print_count([(max_6, 2), (max_5, max(0, n // 5 - 2))])
    elif n % 5 == 3:
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_6, max_7):
            if piece_num[6] & alist:
                print_count([(max_7, 1), (max_6, 1), (max_5, max(0, n // 5 - 2))])
            else:
                print_count([(max_7, 4), (max_5, max(0, n // 5 - 5))])
        else:
            print_count([(max_6, 3), (max_5, max(0, n // 5 - 3))])
    elif n % 5 == 4:
        max_6 = safe_max(piece_num[6] & alist)
        max_7 = safe_max(piece_num[7] & alist)
        if max_7 == max(max_6, max_7):
            print_count([(max_7, 2), (max_5, max(0, n // 5 - 2))])
        else:
            print_count([(max_6, 4), (max_5, max(0, n // 5 - 4))])

elif piece_num[6] & alist:
    max_6 = max(piece_num[6] & alist)
    if n % 6 == 0:
        print(str(max_6) * (n // 6))
    else:
        count_7 = n % 6
        max_7 = max(piece_num[7] & alist)
        print_count([(max_7, count_7), (max_6, max(0, n // 6 - count_7))])

else:
    max_7 = max(piece_num[7] & alist)
    print(str(max_7) * (n // 7))

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

numbers = [None, 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:
        j = i + numbers[a]
        if j <= N:
            dp[j] = max(dp[j], dp[i]*10 + a)
print(dp[N])

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)


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

num_dict = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}
A.sort(reverse=True)


dp = defaultdict(lambda: -1e18)
dp[0] = 0

for i in range(2, N+1):
    dp[i] = max([dp[i-num_dict[a]]+1 for a in A])

num_count = dp[N]

out_list = []
res_N = N
for _ in range(num_count):
    for a in A:
        if dp[res_N]-1 == dp[res_N-num_dict[a]]:
            out_list.append(str(a))
            res_N = res_N - num_dict[a]
            break

print(''.join(out_list))

Solution (Python):
v=[-1,2,5,5,4,5,6,3,7,6]

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

dp=[0]*(N+999)
mp=[[] for _ in range(N+999)]

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))

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

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

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


def matchnum(n):
    table = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return table[n - 1]



dp = [0] + [-INF for _ in range(N)]
for i in range(N + 1):
    for j, a_j in enumerate(A):
        if i - matchnum(a_j) >= 0:
            dp[i] = max(dp[i], dp[i - matchnum(a_j)] + 1)

l = dp[N]
m = N
ans = []
A = sorted(A, reverse=True)
while m > 0:
    for i, a_i in enumerate(A):
        if m - matchnum(a_i) >= 0 and dp[m - matchnum(a_i)] == l - 1:
            ans.append(str(a_i))
            m -= matchnum(a_i)
            l -= 1
            break
print(''.join(ans))

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

INF= 10 ** 9
d_t = {
    1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6
}




d = dict()
for a in A:
    d[a] = d_t[a]

if 2 in A and (3 in A or 5 in A):
    d.pop(2)

if 3 in A and 5 in A:
    d.pop(3)

if 6 in A and 9 in A:
    d.pop(6)





dp = [-INF] * (N + 1)
dp[0] = 0
for i in range(1, N+1):
    for m in d.values():
        if i-m >=0 and dp[i-m] >= 0:
            dp[i] = max(dp[i], dp[i-m] + 1) 





desc_d = sorted(d.items(), key = lambda x: x[0], reverse=True)
s = ''
r = N
for i in range(dp[N]):
    for k, v in desc_d:
        
        if r < v:
            continue

        
        if dp[r] == dp[r-v] + 1:
            s += str(k)
            r -= v
            break

print(s)

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

A = list(map(int,input().split()))
sorted(A)
B =[0,2,5,5,4,5,6,3,7,6]
C =[]
for i in A:
    C.append(B[i])
dp = [-1]*(N+1)
dp[0] = 0
for i in range(N+1):
    for a in range(len(C)):
        if i+C[a]<=N and 0<=dp[i]:
            dp[i+C[a]] = max(dp[i]*10+A[a],dp[i+C[a]])
print(dp[-1])

Solution (Python):
import sys

def chk(i,j):
    tmp=[p[i][k] for k in range(M)]
    tmp[j]=p[i][j]+1
    for k in range(M-1,-1,-1):
        if tmp[k] > p[i+x[j]][k] :
            p[i+x[j]]=[tmp[k] for k in range(M)]

N,M=map(int,input().split())
x=[0,2,5,5,4,5,6,3,7,6]
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(M):
    for j in range(M):
        if x[a[j]]==x[a[i]]: tmp=j
    b.append(a[tmp]) 

a=list(set(b))
a.sort()
M=len(a)
x=[ x[a[i]] for i in range(M) ]

p=[-100 for i in range(N+10)]
p[0]=0
for i in range(N):
    if p[i]>-1:
        for j in range(M):
            p[i+x[j]]=max(p[i+x[j]],p[i]+1)

ans=""
while N>0:
    for j in range(M-1,-1,-1):
        if p[N]==p[N-x[j]]+1:
            ans+=str(a[j])
            N-=x[j]
            break
print(ans)

Solution (Python):
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
list=[]
L=[]
for key in range(9,0,-1):
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[0],reverse=True)
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num+1)] for j in range(N+1)]
dp[0]=[0]*(num+1)

Non=[-1]*(num+1)
for i in range(N):
    ini=[]
    for j in range(num):
        if i+1-cost[j]>=0 and dp[i+1-cost[j]]!=Non:
            a=dp[i+1-cost[j]][:]
            a[j+1]+=1
            a[0]+=1
            ini.append(a)
    if ini:
        dp[i+1]=max(ini)
s=""


for l in L:
    for i in range(num):
        key,cost=list[i]
        if l==key:
            s+=str(key)*dp[N][i+1]

print(s)

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

import sys
sys.setrecursionlimit(50000)

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1, n + 1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if bef == 0:
                lst.append(dig[bef])
            else:
                if dig[bef] > 0:
                    lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""


def dp(i):
    k = -1
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[i] == 1:
            if bef == 0:
                maxi = max(maxi, num)
                k = 0
        else:
            if bef >= 0:
                if dig[bef] == dig[i] - 1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    if k >= 0:
        dp(k)


dp(n)
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())), reverse=True)
match = [[0,0], [1,2], [2,5], [3,5], [4,4], [5,5], [6,6], [7,3], [8,7], [9,6]]

value = []
cost = []
for i in range(len(a)):
        value.append(a[i])
        cost.append(match[a[i]][1])

dp = ["0"]*(n+1)
dp[0] = ""
for i in range(1,n+1):
    for j in range(len(value)):
        tmp_dp_i = 0
        if i - cost[j] >= 0:
            if i - cost[j] >= 0 and dp[i - cost[j]] != "0":
                tmp_dp_i = str(value[j]) + dp[i-cost[j]]
                if len(dp[i]) < len(tmp_dp_i):
                    dp[i] = tmp_dp_i
                elif dp[i] < tmp_dp_i:
                    dp[i] = tmp_dp_i
print(dp[n])

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

Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
for a in sorted(A, reverse=True):
    c = Matches[a]
    for i in range(N - c + 1):
        if dp[i] == -1:
            continue
        dp[i+c] = max(dp[i+c], dp[i] * 10 + a)

print(dp[N])

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

import sys
INT_MIN = sys.maxsize * -1
match = [-100,2,5,5,4,5,6,3,7,6]
CHOICES = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    CHOICES.append([i, match[i]])
CHOICES.sort(reverse=True)

ans = [0]

for i in range(1,N+1):
    ans.append(INT_MIN)
    for c in CHOICES:
        
        
        
        

        if i - c[1] >= 0 and ans[i - c[1]] != INT_MIN:
            ans[i] = max(ans[i], c[0] + ans[i - c[1]] * 10)

print(ans[N])

Solution (Python):
INF = 2**50
def solve(n, m, a):
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp = [-INF] * (n+10)
    dp[0] = 0
    for d in range(n+1):
        for i in range(m):
            nd = d + c[a[i]]
            dp[nd] = max(dp[nd], 10*dp[d] + a[i])
    return dp[n]

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

Solution (Python):
import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    sorted_A = sorted(A)[::-1]
    dp = fill_dp(N,sorted_A)
    array = find_array(dp,N,sorted_A)
    return "".join(map(str,array))

def fill_dp(N,A):
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    return dp

def fill(A,dp,n,N):
    cand = [ dp[n-RESOURCE_DICT[num]]+1 for num in A if n - RESOURCE_DICT[num] >= 0 ]
    dp[n] = max(cand) if len(cand) > 0  else -100*N

def find_array(dp,N,sorted_A):
    array = []
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A:
            if current_n-RESOURCE_DICT[number] >= 0  and dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

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

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

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

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

n = N
while n > 0:
    for j in A:
        if n - V[j] < 0: continue
        if dp[n] == dp[n - V[j]] + 1:
            print(j, end='')
            n = n - V[j]
            break
print()

Solution (Python):
def solve(n, a_list):
    numbers_map = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    usable_map = {}
    for a in a_list:
        usable_map[a] = numbers_map[a]

    
    inf = 1000
    dp = [0] + [-inf for _ in range(n)]
    for value in usable_map.values():
        if value <= n:
            dp[value] = 1

    
    for cost in range(1, n + 1):
        for value in usable_map.values():
            if cost - value < 0 or dp[cost - value] == 0:
                continue
            dp[cost] = max(
                dp[cost],
                dp[cost - value] + 1
            )

    
    buff = []
    digit = n
    reverse_usable_list = sorted(usable_map.items(), reverse=True)
    while True:
        for num, value in reverse_usable_list:
            if digit - value < 0 or dp[digit] - 1 != dp[digit - value]:
                continue
            buff.append(str(num))
            digit -= value
            break
        if digit <= 0:
            break

    return "".join(buff)


def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans = solve(n, a_list)
    print(ans)


main()

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


def num(k):
    costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return costs[k-1]




inf = 1000

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

cost_list = [num(k) for k in A]
for i in range(1, N+1):
    for cost in cost_list:
        if i - cost < 0:
            pass
        else:
            temp = dp[i - cost] + 1
            dp[i] = max(dp[i], temp)

ans = ''
many = N
for d in range(dp[N]): 
    for k in sorted(A, reverse=True):
        if many - num(k) < 0:
            pass
        else:
            if dp[many - num(k)] == dp[many] - 1:
                ans += str(k)
                many -= num(k)
                break
            else:
                pass

print(int(ans))

Solution (Python):
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a or 2 in a and 3 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 6 in a and 9 in a:
        a.remove(6)
    a = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(a[0]) * (n // needs[a[0]])
    n %= needs[a[0]]
    while n > 0:
        use = [_b for _b in a if needs[_b] <= needs[a[0]] + n]
        if len(use) == 1:
            base = base[:-1]
            n += needs[a[0]]
            continue
        flag = max(use) == a[0]
        tmp_n = use[-1] if flag else max(use)
        tmp_c = n // (needs[tmp_n] - needs[a[0]])
        if flag:
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
        else:
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            index += tmp_c
        n -= (needs[tmp_n] - needs[a[0]]) * tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))