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):
def main():
    C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] + [-1] * N
    K = {a: C[a - 1] for a in A}

    for i in range(min(K.values()), N + 1):
        try:
            dp[i] = max(dp[i - v] * 10 + k for k, v in K.items() if i - v >= 0 and dp[i - v] >= 0)
        except ValueError:
            dp[i] = -1
    print(dp[N])
main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    Match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    
    dp = [(0, 0)] * (N + 1) 
    for n in range(N + 1):
        for a in A:
            if n - Match[a] < 0: continue
            if n - Match[a] == 0:
                dp[n] = max(dp[n], (a, 1))
                continue
            number, l = dp[n - Match[a]]
            if number != 0: dp[n] = max(dp[n], (number + a * 10**l, l + 1))
    print(dp[N][0])

if __name__ == "__main__":
    main()

Solution (Python):


import sys






from collections import Counter              











from copy import copy, deepcopy                    



def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    A = lmi()
    
    if 6 in A and 9 in A:
        A.remove(6)
    if 2 in A and 5 in A:
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 2 in A and 3 in A:
        A.remove(2)    

    
    num_to_match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
    match_to_num = dict()
    for num in A:
        match_to_num[num_to_match[num]] = num

    
    needed_match = [num_to_match[num] for num in A]

    
    dp = [[None, None] for _ in range(n + 1)]
    dp[0][0] = 0
    dp[0][1] = Counter()

    def counter_gt(c1, c2):
        
        return sorted(tuple(c1.items()), key=lambda x: x[0], reverse=True) > sorted(tuple(c2.items()), key=lambda x: x[0], reverse=True)

    for i in range(n + 1):
        digit_max = 0
        counter_memo = None
        for match in needed_match:
            if i - match >= 0 and dp[i - match][0] is not None:
                tmp = copy(dp[i - match][1])
                tmp[match_to_num[match]] += 1
                if dp[i - match][0] + 1 > digit_max or (dp[i - match][0] + 1 == digit_max and counter_gt(tmp, counter_memo)):
                    digit_max = dp[i - match][0] + 1
                    counter_memo = copy(dp[i - match][1])
                    counter_memo[match_to_num[match]] += 1 

        if digit_max != 0:
            dp[i][0] = digit_max
            dp[i][1] = counter_memo

    
    
    
    
    char_array = [None] * dp[n][0]
    cnt = 0
    t = sorted(dp[n][1].items(), key=lambda x: x[0], reverse=True)
    for k, v in t:
        for i in range(v):
            char_array[i + cnt] = str(k)
        cnt += v
    print(''.join(char_array))




if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    needs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)

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

    
    for a in A:
        na = needs[a-1]
        for i in range(N+1):
            if i-na >= 0:
                if dp[i-na] == -1:
                    continue
                dp[i] = max(dp[i], dp[i-na]*10+a)

    print(dp[N])


resolve()

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

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

dp = [-1] * (N + 10)
dp[0] = 0
for i in range(N + 1):
    if dp[i] == -1:
        continue
    for a in A:
        dp[i + M_lst[a]] = max(dp[i + M_lst[a]], dp[i] * 10 + a)
print(dp[N])

Solution (Python):


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_list[a])
MA.sort(key=lambda x: x[0], reverse=True)


dp = [-1] * (N+1)
dp[0] = 0
for i in range(N+1):
    for j in range(M):
        if i-MA[j][1] >= 0:
            dp[i] = max(dp[i], dp[i-MA[j][1]] + 1)

remain_keta = dp[N]
remain_match = N
ans = ''
for i in range(dp[N]):
    for ma in MA:
        
        
        if remain_match >= ma[1] and dp[remain_match - ma[1]] == remain_keta - 1:
            ans +=  ma[0]
            remain_keta -= 1
            remain_match -= ma[1]
            break

print(ans)

Solution (Python):

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 = []  
    while dp[k]:
        for Ai in A:
            if k - mn[Ai] >= 0 and 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))  
    M = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(M)]  
    solve(N, M, A)


if __name__ == '__main__':
    main()

Solution (Python):
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 and dp[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 n_match - ma < 0:
                continue
            if max_l[n_match - ma] == max_l[n_match] - 1:
                digits[i] = a
                n_match -= ma
                break
    print(''.join(map(str, digits)))


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
matchlist = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
numberlist = []
for i in range(m):
    numberlist.append(matchlist[a[i]])
numberlist = set(numberlist)

dp = [-10000000]*(n+1)
dp[0] = 0
for i in range(n):
    for j in numberlist:
        if i+j <= n:
            dp[i+j] = max(dp[i+j], dp[i]+1)


ans = []
d = dp[n]
a.sort(reverse = True)
for i in range(d):
    for j in a:
        if n - matchlist[j] >= 0:
            if dp[n] == dp[n-matchlist[j]] + 1:
                n -= matchlist[j]
                ans.append(j)
                break
print("".join(map(str,ans)))

Solution (Python):
from collections import defaultdict

def f(a, b):
    for i in range(9,0,-1):
        if a[i] == b[i]: continue
        elif a[i] > b[i]:
            return True
        else:
            return False
    return False

N, M = map(int, input().split())
se = set()
A = list(map(int, input().split()))
toNum = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[] for i in range(N+1)]
done = [False for i in range(N+10)]
done[N] = True
dics = [defaultdict(int) for i in range(N+1)]
for i in range(N-1, -1, -1):
    for a in A:
        num = toNum[a]
        if not done[i+num]: continue
        l = len(dp[i+num])+1
        d = dics[i+num].copy()
        d[a] += 1
        if l > len(dp[i]) or (l == len(dp[i]) and f(d, dics[i])):
            dp[i] = dp[i+num] + [a]
            done[i] = True
            dics[i] = d
dp[0].sort(reverse=True)
print(*dp[0], sep='')

Solution (Python):
from collections import defaultdict

def f(a, b):
    for i in range(9,0,-1):
        if a[i] == b[i]: continue
        elif a[i] > b[i]:
            return True
        else:
            return False
    return False

N, M = map(int, input().split())
se = set()
A = list(map(int, input().split()))
toNum = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[] for i in range(N+1)]
done = [False for i in range(N+10)]
done[N] = True
dics = [defaultdict(int) for i in range(N+1)]
for i in range(N-1, -1, -1):
    for a in A:
        num = toNum[a]
        if not done[i+num]: continue
        l = len(dp[i+num])+1
        d = dics[i+num].copy()
        d[a] += 1
        if l > len(dp[i]) or (l == len(dp[i]) and f(d, dics[i])):
            dp[i] = dp[i+num] + [a]
            done[i] = True
            dics[i] = d
dp[0].sort(reverse=True)
print(*dp[0], sep='')

Solution (Python):

import sys
input = sys.stdin.readline









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


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


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



dp[0] = 0
for a in A:
    if num[a] <= N:
        dp[num[a]] = 1


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


A.sort(reverse=True)
ans = ""
for i in range(dp[N]):
    for a in A:
        if N-num[a] >= 0 and dp[N-num[a]] == dp[N]-1:
            ans += str(a)
            N -= num[a]
            break

print(ans)

Solution (Python):
from collections import defaultdict
N,M,*A = map(int, open(0).read().split())
ls = [0]*10
ls[1] = 2
ls[2] = 5
ls[3] = 5
ls[4] = 4
ls[5] = 5
ls[6] = 6
ls[7] = 3
ls[8] = 7
ls[9] = 6
dic = defaultdict(int)
for a in A:
  k = ls[a]
  dic[k] = max(dic[k],a)
dp = [-1]*(N+1)
for k in dic.keys():
  if k>N:
    continue
  dp[k] = dic[k]
for i in range(N+1):
  for k in dic.keys():
    if i-k>0 and dp[i-k]!=-1:
      m = dp[i-k]*10+dic[k]
      dp[i] = max(dp[i], m)
print(dp[N])

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

if 1 in A:
    if N%2==0:
        print("1"*(N//2))
    else:
        if 7 in A:
            print("7"+"1"*(N//2-1))
        elif 5 in A:
            print("5"+"1"*(N//2-2))
        elif 3 in A:
            print("3"+"1"*(N//2-2))
        elif 2 in A:
            print("2"+"1"*(N//2-2))
        else:
            print("8"+"1"*(N//2-3))
elif 7 in A:
    if N%3==0:
        print("7"*(N//3))
    elif N%3==1:
        if 4 in A:
            print("7"*(N//3-1)+"4")
        elif 8 in A:
            print("8"+"7"*(N//3-2))
        elif 5 in A:
            print("7"*(N//3-3)+"55")
        elif 3 in A:
            print("7"*(N//3-3)+"33")
        elif 2 in A:
            print("7"*(N//3-3)+"22")
    else:
        if 5 in A:
            print("7"*(N//3-1)+"5")
        elif 3 in A:
             print("7"*(N//3-1)+"3")
        elif 2 in A:
            print("7"*(N//3-1)+"2")
        elif 4 in A:
            print("7"*(N//3-2)+"44")
        elif 8 in A:
            print(print("7"*(N//3-4)+"88"))

else:
    B=[[] for i in range(0,10)]
    for i in range(0,M):
        if 2 in A:
            B[5].append(2)
        if 3 in A:
            B[5].append(3)
        if 4 in A:
            B[4].append(4)
        if 5 in A:
            B[5].append(5)
        if 6 in A:
            B[6].append(6)
        if 8 in A:
            B[7].append(8)
        if 9 in A:
            B[6].append(9)


    dp=['n' for i in range(0,max(10,N+1))]
    for i in range(0,min(N+1,10)):
        if i==2:
            if 2 in A:
                dp[5]='2'
        if i==3:
            if 3 in A:
                dp[5]='3'
        if i==4:
            if 4 in A:
                dp[4]='4'
        if i==5:
            if 5 in A:
                dp[5]='5'
        if i==6:
            if 6 in A:
                dp[6]='6'
        if i==8:
            if 8 in A:
                dp[7]='8'
        if i==9:
            if 9 in A:
                dp[6]='9'

    if N>=6:
        a='0'
        b='0'
        c='0'
        if dp[6]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            x=max(a,b,c)
            if x!=0:
                dp[6]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(dp[6])
            dp[6]=str(max(a,b,c,d))

    if N>=7:
        a='0'
        b='0'
        c='0'
        d='0'
        if dp[7]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            x=max(a,b,c,d)
            if x!=0:
                dp[7]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            e=int(dp[7])
            dp[7]=str(max(e,a,b,c,d))

    for i in range(8,N+1):
        a='0'
        b='0'
        c='0'
        d='0'
        e='0'
        f='0'
        if B[4] and dp[i-4]!='n':
            c='4'+dp[i-4]
        if B[5] and dp[i-5]!='n':
            d=str(max(B[5]))+dp[i-5]
        if B[6] and dp[i-6]!='n':
            e=str(max(B[6]))+dp[i-6]
        if B[7] and dp[i-7]!='n':
            f='8'+dp[i-7]
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        e=int(e)
        f=int(f)
        x=max(a,b,c,d,e,f)
        if x==0:
            dp[i]='n'
        else:
            dp[i]=str(x)
    print(int(dp[N]))

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

if 1 in A:
    if N%2==0:
        print("1"*(N//2))
    else:
        if 7 in A:
            print("7"+"1"*(N//2-1))
        elif 5 in A:
            print("5"+"1"*(N//2-2))
        elif 3 in A:
            print("3"+"1"*(N//2-2))
        elif 2 in A:
            print("2"+"1"*(N//2-2))
        else:
            print("8"+"1"*(N//2-3))
else:
    B=[[] for i in range(0,10)]
    for i in range(0,M):
        if 2 in A:
            B[5].append(2)
        if 3 in A:
            B[5].append(3)
        if 4 in A:
            B[4].append(4)
        if 5 in A:
            B[5].append(5)
        if 6 in A:
            B[6].append(6)
        if 7 in A:
            B[3].append(7)
        if 8 in A:
            B[7].append(8)
        if 9 in A:
            B[6].append(9)


    dp=['n' for i in range(0,max(10,N+1))]
    for i in range(0,min(N+1,10)):
        if i==2:
            if 2 in A:
                dp[5]='2'
        if i==3:
            if 3 in A:
                dp[5]='3'
        if i==4:
            if 4 in A:
                dp[4]='4'
        if i==5:
            if 5 in A:
                dp[5]='5'
        if i==6:
            if 6 in A:
                dp[6]='6'
        if i==7:
            if 7 in A:
                dp[3]='7'
        if i==8:
            if 8 in A:
                dp[7]='8'
        if i==9:
            if 9 in A:
                dp[6]='9'

    if N>=6:
        a='0'
        b='0'
        c='0'
        if B[3]!=[]:
            b='77'
        if dp[6]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            x=max(a,b,c)
            if x!=0:
                dp[6]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(dp[6])
            dp[6]=str(max(a,b,c,d))

    if N>=7:
        a='0'
        b='0'
        c='0'
        d='0'
        if B[3]!=[] and dp[4]!='n':
            b='7'+dp[4]
        if B[4]!=[] and dp[3]!='n':
            c='47'
        if dp[7]=='n':
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            x=max(a,b,c,d)
            if x!=0:
                dp[7]=str(x)
        else:
            a=int(a)
            b=int(b)
            c=int(c)
            d=int(d)
            e=int(dp[7])
            dp[7]=str(max(e,a,b,c,d))

    for i in range(8,N+1):
        a='0'
        b='0'
        c='0'
        d='0'
        e='0'
        f='0'
        if B[3] and dp[i-3]!='n':
            b='7'+dp[i-3]
        if B[4] and dp[i-4]!='n':
            c='4'+dp[i-4]
        if B[5] and dp[i-5]!='n':
            d=str(max(B[5]))+dp[i-5]
        if B[6] and dp[i-6]!='n':
            e=str(max(B[6]))+dp[i-6]
        if B[7] and dp[i-7]!='n':
            f='8'+dp[i-7]
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        e=int(e)
        f=int(f)
        x=max(a,b,c,d,e,f)
        if x==0:
            dp[i]='n'
        else:
            dp[i]=str(x)
    print(int(dp[N]))

Solution (Python):
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

INF = 10 ** 8
dp = [-INF for _ in range(N+1)]
dp[0] = 0

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

ans = 0
digit = dp[N]

for i in range(digit-1, -1, -1):
    if i != 0:
        for a in A:
            if dp[N-d[a]] == i:
                ans = ans * 10 + a
                N -= d[a]
                break
    else:
        for a in A:
            if N == d[a]:
                ans = ans * 10 + a
                break
print(ans)

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

d1 = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
d2 = {2:[1],3:[7],4:[4],5:[5,3,2],6:[9,6],7:[8]}


dp = [-float('inf') for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
  for ai in a:
    if i-d1[ai] >= 0:
      dp[i] = max(dp[i-d1[ai]]+1,dp[i])

a.sort(reverse = True)
ans = ''
r = n
k = dp[n]
while(r > 0):
  for ai in a:
    if r-d1[ai] >= 0 and dp[r-d1[ai]] == k-1:
      ans += str(ai)
      r -= d1[ai]
      k -= 1
      break

print(ans)

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

T=[0,2,5,5,4,5,6,3,7,6]
B=[]
for i in A:
    B.append(T[i])
B=sorted(list(set(B)))
dp=[0 for i in range(N+1)]
AB=[[i,T[i]] for i in A]
AB=sorted(AB,reverse=True)

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



c=N
U=[0 for i in range(8)]
while c>0:
    for i in range(len(AB)):
        if c-AB[i][1]>=0 and dp[c]==dp[c-AB[i][1]]+1:
            U[AB[i][1]]+=1
            c-=AB[i][1]
            break


ans=""
if 9 in A:
    ans+='9'*U[6]
    U[6]=0
if 8 in A:
    ans+='8'*U[7]
if 7 in A:
    ans+='7'*U[3]
if 6 in A:
    ans+='6'*U[6]
if 5 in A:
    ans+='5'*U[5]
    U[5]=0
if 4 in A:
    ans+='4'*U[4]
if 3 in A:
    ans+='3'*U[5]
    U[5]=0
if 2 in A:
    ans+='2'*U[5]
if 1 in A:
    ans+='1'*U[2]

print(ans)

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

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    d = [-1,2,5,5,4,5,6,3,7,6]
    
    keta = [-1]*(N+10)
    keta[0] = 0
    
    for i in range(N):
        for num in a:
            if keta[i] != -1:
                keta[i+d[num]] = keta[i]+1

    use = N
    
    ans = [-1]*(N+10)
    ans[0] = 0
    for i in range(N):
        for num in a:
            if keta[i+d[num]] == keta[i]+1:
                ans[i+d[num]] = max(ans[i+d[num]],ans[i]*10+num)
    
    print(ans[N])
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
d=dict()
need=[0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    if need[a[i]] not in d:
        d[need[a[i]]]=a[i]
    else:
        if a[i]>d[need[a[i]]]:
            d[need[a[i]]]=a[i]
d=list(d.items())
d.sort()
m=len(d)
dp=[[-1]*10 for _ in range(n+1)]
dp[0]=[0]*10
for i in range(n+1):
    for j in range(m):
        if i-d[j][0]>=0 and dp[i-d[j][0]][0]!=-1:
            if dp[i][0]==dp[i-d[j][0]][0]+1:
                ok=False
                for k in reversed(range(1,10)):
                    if k==d[j][1]:
                        if dp[i][k]<dp[i-d[j][0]][k]+1:
                            ok=True
                            break
                        if dp[i][k]>dp[i-d[j][0]][k]+1:
                            break
                    else:
                        if dp[i][k]<dp[i-d[j][0]][k]:
                            ok=True
                            break
                        if dp[i][k]>dp[i-d[j][0]][k]:
                            break
                if ok:
                    for k in range(10):
                        dp[i][k]=dp[i-d[j][0]][k]
                    dp[i][d[j][1]]+=1
                    dp[i][0]+=1
            elif dp[i][0]<dp[i-d[j][0]][0]+1:
                for k in range(10):
                    dp[i][k]=dp[i-d[j][0]][k]
                dp[i][d[j][1]]+=1
                dp[i][0]+=1
ans=str()
for i in reversed(range(1,10)):
    ans+=str(i)*dp[-1][i]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
INF = float("inf")


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse=True)  
    cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    
    dp = [-1] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for aj in a:
            if i - cost[aj] < 0:
                continue
            dp[i] = max(dp[i], dp[i - cost[aj]] + 1)
    digits = dp[n]
    ans = ""
    rest = n
    
    while digits:
        for aj in a:
            if rest - cost[aj] < 0:
                continue
            if dp[rest - cost[aj]] == digits - 1:
                ans += str(aj)
                rest -= cost[aj]
                digits -= 1
                break
    print(ans)


if __name__ == '__main__':
    main()

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

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

def ketadp(N,M,A):
  dp=[0]*(N+1)
  for i in range(N):
    for j in A:
      if (i+1-honsuu[j])==0 or (i+1-honsuu[j]>0 and dp[i+1-honsuu[j]]!=0):
        dp[i+1]=max(dp[i+1],dp[i+1-honsuu[j]]+1)
  return dp
  

ans=""
keta=ketadp(N,M,A)
remain=keta[N]
match=N


while(match>0):
  for i in A:
    
    if match-honsuu[i]<0:
      continue;
    if(keta[match-honsuu[i]]==remain-1) and not (match-honsuu[i]!=0 and remain==1):
      ans+=str(i)
      remain-=1
      match-=honsuu[i]
      break;
print(ans)

Solution (Python):
import math
from collections import Counter
n, m = map(int, input().split())
a = list(map(int, input().split()))

if 9 in a and 6 in a:
    a.remove(6)
if 5 in a:
    if 2 in a:
        a.remove(2)
    if 3 in a:
        a.remove(3)
if 3 in a and 2 in a:
    a.remove(2)

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

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

int_dp = [0] * (n+1)

for i in range(1, n+1):
    for j in a:
        if i >= req_m[j] and dp[i-req_m[j]] is not None:
            v = dp[i-req_m[j]] + Counter([j])
            if dp[i] is None:
                dp[i] = v
            else:
                if sum(dp[i].values()) < sum(v.values()):
                    dp[i] = v
                elif sum(dp[i].values()) == sum(v.values()):
                    if sorted(dp[i].elements(), reverse=True) < sorted(v.elements(), reverse=True):
                        dp[i] = v

print(''.join(map(str, sorted(dp[-1].elements(), reverse=True))))

Solution (Python):

N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
f = [-1, 2,5,5,4,5,6,3,7,6] 


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

keta = dp[N]
ans = ""
matchs = N

while keta>0:
    for aj in A:
        if matchs-f[aj] < 0: continue
        if dp[matchs-f[aj]] == keta-1:
            ans += str(aj)
            matchs -= f[aj]
            keta -= 1
            break
print(ans)

Solution (Python):

N,M = map(int, input().split())
A = list(map(int, input().split()))
f = [-1, 2,5,5,4,5,6,3,7,6] 


dp = [None]*(N+1)
dp[0] = ""


def max_str(s1:str, s2:str)->str:
    """return bigger one"""
    l1, l2 = len(s1), len(s2)
    if l1 != l2:
        return s1 if l1>l2 else s2
    if l1 == l2: 
        return s1 if s1>s2 else s2
    
for i in range(2, N+1):
    nxt = ""
    for aj in A:
        
        if i-f[aj]<0 or dp[i-f[aj]]==None: continue
        nxt = max_str(nxt, 
                      dp[i-f[aj]]+str(aj))
    if nxt!="":
        dp[i] = nxt
    
print(dp[N])

Solution (Python):

N,M = map(int, input().split())
A = list(map(int, input().split()))
f = [-1, 2,5,5,4,5,6,3,7,6] 


dp = [None]*(N+1)
dp[0] = ""


def max_str(s1:str, s2:str)->str:
    """return bigger one"""
    l1, l2 = len(s1), len(s2)
    if l1 != l2:
        return s1 if l1>l2 else s2
    if l1 == l2: 
        return s1 if s1>s2 else s2
    
for i in range(2, N+1):
    nxt = ""
    for aj in A:
        
        if i-f[aj]<0 or dp[i-f[aj]]==None: continue
        nxt = max_str(nxt, 
                      dp[i-f[aj]]+str(aj))
    if nxt!="":
        dp[i] = nxt
    
print(dp[N])

Solution (Python):
def max_for_str(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:
        for c1, c2 in zip(a, b):
            if c1 > c2:
                return a
            elif c1 < c2:
                return b
        return a
            
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

dp = [None] * (N+1)
dp[0] = ""

for i in range(N+1):
    for A in As:
        if i - match[int(A)] >= 0 and not dp[i - match[int(A)]] is None:
            if dp[i] is None:
                dp[i] = A + dp[i - match[int(A)]]
            else:
                dp[i] = max_for_str(dp[i] , A + dp[i - match[int(A)]])

print(dp[N])

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

dp = [-1**10]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    
    for j in range(m):
        if i >= l[a[j]] and dp[i] < dp[i-l[a[j]]]+1:
            dp[i] = dp[i-l[a[j]]]+1
            

ans = []
remain = dp[-1]
now = n
for i in a:
    x = l[i]
    while now -x >= 0 and dp[now] == dp[now-x]+1:
        ans.append(i)
        now -= x 
print(*ans,sep="")

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
A = lr()
A.sort(reverse=True)
dp = [-1] * (N+1)
dp[0] = 0
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for a in A:
    for x in range(1, N+1):
        y = match[a]
        if x - y < 0 or dp[x-y] == -1:
            continue
        dp[x] = max(dp[x], dp[x-y] * 10 + a)

answer = dp[N]
print(answer)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()
dp = [-1] * (N+1)
dp[0] = 0
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for x in range(N):
    for a in A:
        y = match[a]
        if x + y > N:
            continue
        dp[x+y] = max(dp[x+y], dp[x] * 10 + a)

answer = dp[N]
print(answer)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()
dp = [-1] * (N+1)
dp[0] = 0
for x in range(N):
    for a in A:
        y = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6][a]
        if x + y > N:
            continue
        dp[x+y] = max(dp[x+y], dp[x] * 10 + a)

answer = dp[N]
print(answer)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, M = lr()
A = lr()
matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = [(matches[a], a) for a in A]
A.sort(key = lambda x: x[1], reverse=True)
A.sort(key = lambda x: x[0])
top_match = A[0][0]
dp = [None] * (N+1)
dp[0] = []
used = set()
for match, num in A:
    if match in used:
        continue
    used.add(match)
    for x in range(N+1):
        if x - match < 0:
            continue
        if dp[x] == None and dp[x-match] != None:
            dp[x] = dp[x-match] + [num]
        elif dp[x] != None and dp[x-match] != None:
            if len(dp[x-match]) >= len(dp[x]):
                dp[x] = dp[x-match] + [num]
            elif len(dp[x-match]) >= 1 and len(dp[x-match]) == len(dp[x]) - 1:
                y = list(map(str, dp[x][::-1])); y.sort(reverse=True)
                z = [str(num)] + list(map(str, dp[x-match][::-1])); z.sort(reverse=True)
                y = int(''.join(y))
                z = int(''.join(z))
                if z > y:
                    dp[x] = dp[x-match] + [num]

X = dp[N]
X.sort(reverse=True)
answer = ''.join(list(map(str, X)))
print(answer)

Solution (Python):
nim,mike = map(int,input().split())
array = list(map(int,input().split()))

dp = [-1 for i in range(nim+10)]
l = [0,2,5,5,4,5,6,3,7,6]
dp[0] = 0
for i in range(nim-1):
    for s in array:
        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[nim])

Solution (Python):


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

    
    nm = [999, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dig = [None for i in range(8)]
    for x in sorted(a):
        dig[nm[x]] = x

    
    dp = [None for j in range(n + 1)]
    dp[0] = (0, None, None)
    for j in range(1, n + 1):  
        for use in [2, 3, 4, 5, 6, 7]:
            jp = j - use
            if jp < 0:
                continue
            if dig[use] is None:
                continue
            if dp[jp] is None:
                continue
            d = dp[jp][0] + 1
            tup = (d, jp, dig[use])
            if (dp[j] is None) or (dp[j][0] < d) or (dp[j][0] == d and dp[j][2] < dig[use]):
                dp[j] = tup

    res = []
    j = n
    while True:
        d, jp, i = dp[j]
        if jp is None:
            break
        res.append(str(i))
        j = jp
    assert len(res) == dp[n][0]

    print("".join(res))

if __name__ == "__main__":
    main()