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,*a=map(int,open(0).read().split())
d=[0]+[-1]*n*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10 for j in a)
print(d[n])

Solution (Python):
N, M = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()                        




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


dp = [-999 for _ in range(N+1)]
dp[0] = 0
for i in range(N+1):
    n = [dp[i-num[a[j]]] for j in range(M) if i-num[a[j]] >= 0]
    if len(n) > 0:
        dp[i] = max(n) + 1



i = N
ans = ""
for _ in range(dp[N]):
    
    
    
    if dp[i] > 1:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] >= 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
    else:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] == 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
        break
    
    i = i-num[b]
    
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=list(map(int,input().split()))
seg0=[0,2,5,5,4,5,6,3,7,6]

import numpy as np

A.sort(reverse=1)
seg=[]
for i in range(m):
    seg.append(seg0[A[i]])



keta=[-np.inf for i in range(n+1)]
keta[0]=0
for i in range(1,n+1):
    for j in range(m):
        if i-seg[j]>=0 :
            keta[i]=max(keta[i],keta[i-seg[j]]+1)



ke=keta[n]



ans=0
while ke>1 :
    for j in range(m):
        
        
        if n-seg[j]>0 and keta[n]==keta[n-seg[j]]+1 :
            ans+=A[j]*10**(ke-1)
            n-=seg[j]
            
            break
    ke-=1


for i in range(m):
    
    if n==seg[i] :
        ans+=A[i]
        break

print(ans)

Solution (Python):
n, m = [int(elem) for elem in input().split()]
a = [elem for elem in input().split()]
a = sorted(a, reverse=True)

num_dict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(n+1)]

for i in range(n+1):
    for strnum in a:
        if i - num_dict[strnum] < 0:
            continue
        if i - num_dict[strnum] == 0 and dp[i] == "":
            dp[i] = strnum
        pre_strnum = dp[i - num_dict[strnum]]
        if pre_strnum != "":
            if len(pre_strnum) + 1 > len(dp[i]):
                dp[i] = pre_strnum + strnum

print("".join(sorted(dp[n], reverse=True)))

Solution (Python):
N, M = [int(i) for i in input().split()]
A = sorted([s for s in input().split()], reverse=True)
numDict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(N + 1)]

for i in range(N + 1):
    for strNum in A:
        if i - numDict[strNum] < 0:
            continue
        if i - numDict[strNum] == 0 and dp[i] == "":
            dp[i] = strNum
        preStrNum = dp[i - numDict[strNum]]
        if preStrNum != "":
            if len(preStrNum) + 1 > len(dp[i]):
                dp[i] = preStrNum + strNum

print("".join(sorted(dp[N], reverse=True)))

Solution (Python):
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
num=[2,5,5,4,5,6,3,7,6]


creat_A=[]
for n in A:
  creat_A.append(num[n-1])


dp=[-1 for _ in range(N+1)]
for i in range(M):
  if creat_A[i] <= N:
    dp[creat_A[i]]=1

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


ans=[0 for _ in range(10)]

now=N
while dp[now] > 0:
  res=-1
  temp_i=-1
  for i in range(M):
    if now-creat_A[i] >0 and dp[now-creat_A[i]]==dp[now]-1:
      if res < A[i]:
        res=A[i]
        temp_i=i
  if res==-1:
    break
  else:
    ans[res]+=1
    now-=creat_A[temp_i]
    
temp2=0
for i in range(M):
  if creat_A[i]==now:
    temp2=max(temp2,A[i])
ans[temp2]+=1


ansans=""
for i in range(10):
  if ans[i]>0:
    ansans+=(str(i)*ans[i])
ansans=ansans[::-1]
print(ansans)

Solution (Python):
n, m = map(int, raw_input().split())
l = map(int, raw_input().split())
dp = [-1]*(n+10)
dp[0] = 0
cost = [0,2,5,5,4,5,6,3,7,6]
for i in range(1, n + 1):
    for j in l:
        if cost[j] <= i:
            dp[i] = max(dp[i], dp[i-cost[j]]*10 + j)
print dp[n]

Solution (Python):

import copy
import numpy as np
import random


































def solve():
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort(reverse = True)
    
    dp = [0] + ([-1]*N)
    
    for i in range(1, N+1):
        for a in A:
            if L[a] <= i:
                
                dp[i] = max(dp[i], dp[i-L[a]] * 10 + a)
    
    print(dp[-1])


if __name__=="__main__":
    solve()

Solution (Python):
def func(latter, remains, former = []):
    
    if remains == 0:
        return sum(x for _,x in former)
    if len(latter) == 0:      
        while True:
            b, p = former.pop()    
            if p==0:               
                latter.append(b)   
            else:             
                break         
        return func(latter, remains+b, former+[(b, p-1)])
    a = latter.pop()
    q, r = divmod(remains, a)
    if r!=0: 
        q = q-1 if q > 0 else 0  
    return func(latter, remains-q*a, former+[(a, q)])

def func2(l, remains, remain_num, ans=[]):
    
    if len(l)>0:
        a, *l = l
        for i in range(min(remains//a, remain_num)+1):
            yield from func2(l, remains-a*i, remain_num-i, [(a, i)]+ans)
    elif remain_num==0 and remains==0:
        yield ans

n, m = map(int, input().split())
s = sorted((int(x) for x in input().split()), reverse=True)
num = [6,2,5,5,4,5,6,3,7,6]
t = sorted({num[i] for i in s}, reverse=True)
t_rev = {x:max(j for j in s if num[j]==x) for x in t}
t_min = t[-1]
m_num = func(t.copy(), n)   
max_replacement = n - m_num*t_min        
min_match_num = max(0, m_num - max_replacement)  
other_num = m_num - min_match_num   
def func3(ans):
    l = {t_rev[x]:(i+min_match_num if x==t_min else i) for x,i in ans}
    return [l[x] for x in sorted(l, reverse=True)]
answer = max(func3(ans) for ans in func2(t.copy(), n-min_match_num*t_min, other_num))
print(*(str(x)*i for x, i in zip(sorted(t_rev.values(), reverse=True), answer)), sep='')

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

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

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

for i in range(N+1):
  for j in A:
    if C[j] <= i:
      dp[i] = max(dp[i-C[j]]*10 + j, dp[i])

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
if 1 in A:
    if 4 in A: A.remove(4)
    if 6 in A: A.remove(6)
    if 9 in A: A.remove(9)
if 3 in A:
    if 2 in A: A.remove(2)
if 5 in A:
    if 3 in A: A.remove(3)
    if 2 in A: A.remove(2)
if 7 in A:
    if 6 in A: A.remove(6)
    if 9 in A: A.remove(9)
if 9 in A:
    if 6 in A: A.remove(6)

def MatchNum(i):
    if i == 1: return 2
    elif i == 4: return 4
    elif i in [2, 3, 5]: return 5
    elif i == 7: return 3
    elif i == 8: return 7
    elif i in [6, 9]: return 6

MatchUse = []
for a in A:
    MatchUse.append((a, MatchNum(a)))

DP = [-1] * (N+1)
for a, num in MatchUse:
    if num <= N: DP[num] = a

for i in range(2, N):
    if DP[i] > 0:
        temp = DP[i]*10
        for a, num in MatchUse:
            if i + num <= N:
                DP[i + num] = max(DP[i + num], a + temp)
print(DP[N])

Solution (Python):
w, n = map(int, input().split())
A0 = list(map(int, input().split()))
C = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = []
for i in range(n):
    A.append([A0[i], C[A0[i]]])

dp = [-1] * (w + 1)
dp[0] = 0
for i in range(w + 1):
    for j in range(n):
        if A[j][1] <= i:
            dp[i] = max(dp[i], dp[i - A[j][1]] * 10 + A[j][0])
            
print(dp[w])

Solution (Python):

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

inf = float('inf')
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] + [-inf] * N
for i in range(N + 1)[1::]:
    for x in A:
        if i >= num[x]:
            dp[i] = max(dp[i], dp[i - num[x]] + 1)

ans = ''
while N > 0:
    for x in A:
        if N >= num[x] and dp[N - num[x]] == dp[N] - 1:
            ans += str(x)
            N -= num[x]
            break

print(ans)

Solution (Python):
from collections import defaultdict

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

match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
mat = []
for i in range(m):
    mat.append((match[a[i]-1], a[i]))

d = defaultdict(int)
for ma, num in mat:
    d[ma] = max(d[ma], num)


INF = float('inf')
dp = [-INF] * (n+10)
dp[0] = 0

for i in range(n):
    if dp[i] == -INF:
        continue
    for ma, num in mat:
        if dp[i] + 1 > dp[i+ma]:
            dp[i+ma] = dp[i] + 1

mat.sort(key=lambda x: x[1], reverse=True)

ans = ""
i = n
while i > 0:
    for ma, num in mat:
        if i - ma < 0:
            continue
        if dp[i] == dp[i-ma] + 1:
            ans += str(num)
            i -= ma
            break

print(ans)

Solution (Python):









import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys


def str_max(s1, s2):
    if len(s1) > len(s2):
        return s1
    elif len(s1) < len(s2):
        return s2
    if s1 > s2:
        return s1
    else:
        return s2


def main():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))
    
    needs = [0,2,5,5,4,5,6,3,7,6]
    need_to_ch = {}
    for a in sorted(As):
        need = needs[a]
        need_to_ch[need] = str(a)
    
    dp = [None for _ in range(N + 1)]
    dp[0] = ''
    for i in range(1, N + 1):
        for need, ch in need_to_ch.items():
            if i - need < 0 or dp[i - need] is None:
                continue
            cand = dp[i - need] + ch
            if dp[i] is None:
                dp[i] = cand
            else:
                dp[i] = str_max(dp[i], cand)
        
    print(dp[N])


main()

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

d = [-1]*(n+1)
d[0] = 0

for i in range(n+1):
    for ai in a:
        if (i - c[ai]) >= 0:
            d[i] = max(d[i], d[i-c[ai]]*10 + ai)

print(d[-1])

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

dp = [-1 for _ in range(10010)]
dp[0] = 0            

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

for i in range(1,10005):
    for x in A:          
        if i-MatchNum[x] >= 0:
            tmp = dp[i-MatchNum[x]]*10 + x
            dp[i] = max(tmp,dp[i])
print(dp[N])

Solution (Python):
import sys

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

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

items = sorted(A, reverse=True)
weights = [K[x] for x in items]

m = [[0]*M] + [None for i in range(N)]
for i in range(1, N+1):
	best = [0]*M
	
	for j in range(M):
		remaining = i - weights[j]
		if remaining >= 0 and m[remaining] is not None and sum(m[remaining])+1 > sum(best):
			best = m[remaining][:j] + [m[remaining][j]+1] + m[remaining][j+1:]
	
	if sum(best) == 0:
		best = None

	m[i] = best

for i in range(M):
	for j in range(m[N][i]):
		sys.stdout.write(str(items[i]))

sys.stdout.write("\n")

Solution (Python):
def greater(a,b):
    if a is None:
        return b
    if len(a)>len(b):
        return a
    if len(b)>len(a):
        return b
    for i in range(len(a)):
        if a[i]>b[i]:
            return a
        if b[i]>a[i]:
            return b
    return a

c={"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
n,m=map(int,input().split())
l=input().split()
l.sort()
max=[None for i in range(10010)]
for a in l:
    max[c[a]]=a
for i in range(2,n):
    if max[i] is not None:
        for a in l:
            k=max[i]+a if max[i][0]>a else a+max[i]
            max[i+c[a]]=greater(max[i+c[a]],k)
print(max[n])

Solution (Python):

def get_match_list(num_list, num_num):
    match_num_list = set()
    match_dic = [2,5,5,4,5,6,3,7,6]
    for num in num_list:
        match_num_list.add(match_dic[num-1])
    match_num_list = list(match_num_list)
    match_num_list.sort()
    return match_num_list

def get_dp(use_match_list, match_nun):
    dp = [-1 for i in range(match_nun + 1)]
    dp[0] = 0
    for i in range(2, match_nun + 1):
        for macth_bar in use_match_list:
            if dp[i-macth_bar] >= 0:
                dp[i] = dp[i-macth_bar] + 1
                break
    return dp

def print_ans(dp, match_nun, num_list):
    match_dic = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    max_ketasuu = dp[match_nun]
    ans = ''
    while match_nun > 0:
        for num in num_list:
            use_match_num = match_dic[num - 1]
            if match_nun - use_match_num < 0:
                continue
            if dp[match_nun - use_match_num] == max_ketasuu - 1:
                ans += str(num)
                match_nun -= use_match_num
                max_ketasuu -= 1
                break
    print(ans)



def main():
    match_nun, num_num = map(int, input().split())
    num_list = list(map(int, input().split()))
    num_list.sort(reverse=True)
    use_match_list = get_match_list(num_list, num_num)
    dp = get_dp(use_match_list, match_nun)
    print_ans(dp, match_nun, num_list)


if __name__ == '__main__':
    main()

Solution (Python):
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])

def main():
    n, m = get_next_ints()
    numbers = get_next_ints()
    costs = [0,2,5,5,4,5,6,3,7,6]
    from collections import defaultdict
    
    cost_number = defaultdict(int)
    for number in numbers:
        cost = costs[number]
        cost_number[cost] = max(cost_number[cost], number)
    use_numbers = cost_number.values()
    costs_numbers = list(zip( cost_number.values(),list(cost_number.keys())))
    costs_numbers.sort(reverse=True)
    
    
    dp = {0:0}
    for i in range(1,n+1):
        answers = []
        for number, cost in costs_numbers:
            if (i - cost) in dp:
                answers.append(dp[(i - cost)])
        if answers:
            dp[i] = max(answers) + 1
    
    digits = []
    
    remain = n
    while remain > 0:
        current = dp[remain]
        for number, cost in costs_numbers:
            if (remain - cost) in dp:
                if dp[(remain - cost)] == current - 1:
                    digits.append(str(number))
                    remain -= cost
                    break
                    
    print("".join(digits))
        
    
if __name__ == '__main__':
    main()

Solution (Python):
import math
def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	
	d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	num2match = {key:val for key, val in d.items() if key in nums}
	
	dp = [-1 for i in range(n + 1)]
	dp_keta = [0 for i in range(n + 1)]

	dp[0] = 0
	val_set = list(set(num2match.values()))
	match2num = {v:max([int(key) for key, val in num2match.items() if val == v]) for v in val_set}

	cnt = 0
	for i in range(2, n + 1):
		for val in val_set:
			
			cnt += 1
			if i >= val and dp[i - val] >= 0:
				tmp = match2num[val] * (10 ** dp_keta[i - val]) + dp[i - val]
				dp[i] = max(dp[i], tmp)
				dp_keta[i] = max(dp_keta[i], dp_keta[i - val] + 1)

	
	
	
	
	print(int(dp[n]))
	
 
if __name__ == '__main__':
	main()

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
A = LIST()
need = [0,2,5,5,4,5,6,3,7,6]

dp = [''] * (N+10)
for a in A:
    dp[need[a]] = max(dp[need[a]], str(a))

for i in range(N):
    if dp[i] != '':
        for a in A:
            
            if len(dp[i+need[a]]) < len(dp[i])+1:
                dp[i+need[a]] = dp[i]+str(a)
            
            elif len(dp[i+need[a]]) == len(dp[i])+1:
                dp[i+need[a]] = max(dp[i+need[a]], dp[i]+str(a))
print(dp[N])

Solution (Python):
def greater(a,b):
    if len(a)>len(b):
        return a
    elif len(b)>len(a):
        return b
    for i in range(len(a)):
        if a[i]<b[i]:
            return b
        if b[i]<a[i]:
            return a
    return a

cost=[0,2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
la=[int(a) for a in input().split()]
la.sort()
sa=[str(a) for a in la]
ca=[cost[a] for a in la]
max=[None for i in range(10010)]
for i in range(m):
    max[ca[i]]=sa[i]
for i in range(2,n):
    if max[i]==None:
        continue
    for j in range(m):
        if max[i][0]>sa[j]:
            k=max[i]+sa[j]
        else:
            k=sa[j]+max[i]
        if max[i+ca[j]]==None:
            max[i+ca[j]]=k
        else:
            max[i+ca[j]]=greater(max[i+ca[j]],k)
print(max[n])

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
honsuu = [0,2,5,5,4,5,6,3,7,6]
aval = []
for a in A:
  aval += [honsuu[a]]
aval.sort()

dp = [0]+ [-float("INF")]*N 

for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    elif dp[i-b] >= 0:
      dp[i] = dp[i-b] + 1
      break
      


A.sort(reverse=True)
ans = []
for i in range(dp[N],0,-1):
  for a in A:
    if N - honsuu[a] < 0:continue
    if dp[N - honsuu[a]] == dp[N] - 1:
      N -= honsuu[a]
      ans += [a]
      break
print(''.join(map(str, ans)))

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
honsuu = [0,2,5,5,4,5,6,3,7,6]
aval = []
for a in A:
  aval += [honsuu[a]]
aval.sort()

dp = [0]+ [-float("INF")]*N 

for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    elif dp[i-b] >= 0:
      dp[i] = dp[i-b] + 1
      break
      


A.sort(reverse=True)
ans = []
for i in range(dp[N],1,-1):
  for a in A:
    if N - honsuu[a] < 0:continue
    if dp[N - honsuu[a]] == dp[N] - 1:
      N -= honsuu[a]
      ans += [a]
      break
      
final = 0
for i in range(10):
  if i in A and honsuu[i] == N:
    final = i
ans += [final]
print(''.join(map(str, ans)))

Solution (Python):

"""
a,b = map(int, input().split())
if b % a == 0:
    print(b + a)
else:
    print(b-a)
"""


"""
n, m = map(int, input().split())
ans = list(map(int, input().split()))
del ans[0]
ans = set(ans)
for i in range(n-1):
    a = list(map(int, input().split()))
    del a[0]
    ans = ans & set(a)
print(len(ans))
"""



"""
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
print(gcd_list(a))
"""


n,m = map(int, input().split())
a = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = [-float("inf") for _ in range(n + 1)]
num_ans = []
a.sort(reverse=True)
for i in a:
    num_ans.append(num[i])
ans[0] = 0
for i in range(n + 1):
    for b in num_ans:
        if i - b >= 0:
            ans[i] = max(ans[i - b] + 1, ans[i])
anse = ""
while ans[n] > 0:
    for k, i in enumerate(num_ans):
        if n - i >= 0:
            
            if ans[n] - 1 == ans[n - i]:
                anse += str(a[k])
                n -= i
                break
    if n < 0:
        break
            
print(anse)

Solution (Python):
n, m = map(int, input().split())
A = list(map(int, input().split()))
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

for i in range(n+1):
    for j in A:
        if i - c[j] >= 0:
            dp[i] = max(dp[i], dp[i - c[j]] * 10 + j)
print(dp[n])

Solution (Python):
def strmax(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:
        return max(a, b)


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [None] * (N+1)
    dp[0] = ""
    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    for i in range(N+1):
        for d in A:
            if i < cost[d]:
                continue
            prev = dp[i - cost[d]]
            if prev is None:
                continue
            else:
                candidate = strmax(prev + str(d),
                                   str(d) + prev)
            if dp[i] is None:
                dp[i] = candidate
            else:
                dp[i] = strmax(dp[i], candidate)
    print(dp[N])


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

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


dp = [-1e+8] * (N + 1)
dp[0] = 0
for i in range(N+1):
    for aa in a:
        if i >= rate[aa]:
            dp[i] = max([dp[i], dp[i-rate[aa]]*10 + aa])
print(dp[-1])

Solution (Python):
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[N])

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

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

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

print(dp[-1])

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

A.sort(reverse=True)

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

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

print(dp[-1])

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



dp = [0] + [-float('inf')] * (N+1)       
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  

for num_match in range( 2, N+1 ):
    for Aj in A:
        if num_match >= cost[Aj]:
            dp[num_match] = max( dp[num_match], dp[num_match-cost[Aj]]+1 )


ans = ""
digit = dp[N]

A.sort( reverse=True )
while N > 0:
    for Ai in A:
        if N-cost[Ai] >=0 and dp[N-cost[Ai]] == digit-1:
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( ans )

Solution (Python):
n, m = map(int,input().split())
a = sorted(map(int,input().split()))[::-1]
c = [0,2,5,5,4,5,6,3,7,6]
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(2, n+1):
    for j in a:
        if i >= c[j]:
            dp[i] = max(dp[i], dp[i-c[j]]+1)
r = []
while n:
    i = max((i for i in a if n>=c[i]), key=lambda x: dp[n-c[x]])
    r.append(i)
    n -= c[i]
print(''.join(map(str, r)))

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

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

dp = [[-1 for n in range(N+1)] for m in range(M+1)]
dp[0][0] = 0

dp_r = [[-1 for n in range(N+1)] for m in range(M+1)]


d = {}
for a in A:
    d[a] = c[a-1]


inv_d = {}
for k,v in d.items():
    if v in inv_d:
        if k > inv_d[v]:
            inv_d[v] = k
    else:
        inv_d[v] = k


s_A = sorted(inv_d.items(), key=lambda x:x[0],reverse=True)

A = [a[1] for a in s_A]
M = len(A)

for m in range(1,M+1):
    for n in range(N+1):
        
        
        if n-c[A[m-1]-1] >= 0 and dp[m][n-c[A[m-1]-1]] != -1:
            if dp[m-1][n] < (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 1
            elif dp[m-1][n] == (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 2
            else:
                dp[m][n] = dp[m-1][n]
                dp_r[m][n] = 0
        else:
            dp[m][n] = dp[m-1][n]
            dp_r[m][n] = 0






def trace(dp,m,n):
    r=[[]]
    for _ in range(N+M+2):
        if m==0 and n==0:
            return r
        elif dp_r[m][n] == 0:
            m = m-1
        elif dp_r[m][n] == 1:
            r = [r_+[m] for r_ in r]
            n = n-c[A[m-1]-1]
        elif dp_r[m][n] == 2:
            r_1 = trace(dp,m-1,n)
            r_2 = trace(dp,m,n-c[A[m-1]-1])
            return [r[0]+r_ for r_ in r_1] + [r[0]+r_+[m] for r_ in r_2]

tm = trace(dp,M,N)

ans = []
for tm_ in tm:
    ans_ = [inv_d[c[A[m-1]-1]] for m in tm_]
    ans_.sort(reverse=True)
    ans += [ans_]

ans.sort(reverse=True)

for ans_ in ans[0]:
    print(ans_,sep='',end='')
print()

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

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

dp = [[-1 for n in range(N+1)] for m in range(M+1)]
dp[0][0] = 0

dp_r = [[-1 for n in range(N+1)] for m in range(M+1)]


d = {}
for a in A:
    d[a] = c[a-1]


inv_d = {}
for k,v in d.items():
    if v in inv_d:
        if k > inv_d[v]:
            inv_d[v] = k
    else:
        inv_d[v] = k


s_A = sorted(inv_d.items(), key=lambda x:x[0])
A = [a[1] for a in s_A]
M = len(A)

for m in range(1,M+1):
    for n in range(N+1):
        
        
        if n-c[A[m-1]-1] >= 0 and dp[m][n-c[A[m-1]-1]] != -1:
            if dp[m-1][n] < (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 1
            elif dp[m-1][n] == (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 2
            else:
                dp[m][n] = dp[m-1][n]
                dp_r[m][n] = 0
        else:
            dp[m][n] = dp[m-1][n]
            dp_r[m][n] = 0






def trace(dp,m,n):
    r=[[]]
    for _ in range(N+M+2):
        if m==0 and n==0:
            return r
        elif dp_r[m][n] == 0:
            m = m-1
        elif dp_r[m][n] == 1:
            r = [r_+[m] for r_ in r]
            n = n-c[A[m-1]-1]
        elif dp_r[m][n] == 2:
            r_1 = trace(dp,m-1,n)
            r_2 = trace(dp,m,n-c[A[m-1]-1])
            return [r[0]+r_ for r_ in r_1] + [r[0]+r_+[m] for r_ in r_2]

tm = trace(dp,M,N)

ans = []
for tm_ in tm:
    ans_ = [inv_d[c[A[m-1]-1]] for m in tm_]
    ans_.sort(reverse=True)
    ans += [ans_]

ans.sort(reverse=True)

for ans_ in ans[0]:
    print(ans_,sep='',end='')
print()

Solution (Python):


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

cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cd = [(a, cost[a]) for a in A]
cd.sort(key=lambda x: x[0], reverse=True)

dp = [0] + [-1] * N
for i in range(1, N + 1):
    for a, c in cd:
        if i - c >= 0 and 0 <= dp[i - c]:
            dp[i] = max(dp[i], dp[i - c] + 1)

ans, i = [], N
for _ in range(dp[-1]):
    for a, c in cd:
        if i - c >= 0 and dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

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

Solution (Python):
from copy import copy
from sys import stdout

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

W, _ = map(int, raw_input().strip().split(' '))

dp = [[0 for _ in xrange(9)] for _ in xrange(W + 1)]

values  = map(int, raw_input().strip().split(' '))
weights = [digit_costs[values[i] - 1] for i in xrange(len(values))]

def is_larger(a, b) : 
    a_s, b_s = sum(a), sum(b)
    if a_s != b_s : 
        if a_s > b_s : 
            return True
        return False

    for i in xrange(8, -1, -1) : 
        if a[i] > b[i] : 
            return True
        if b[i] > a[i] : 
            return False

    return False

for i in xrange(len(values)) : 
    vi = values[i]
    wi = weights[i]
    
    for w in xrange(0, W - wi + 1) : 
        if any(x for x in dp[w]) or not w :
            temp = copy(dp[w])
            temp[vi - 1] += 1
            if is_larger(temp, dp[w + wi]) :
                dp[w + wi] = temp



result = ''
for x in xrange(8, -1, -1) : 
    if dp[-1][x] : 
        result += str(x + 1) * dp[-1][x]

print result

Solution (Python):


import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]

  if len(digits) == 0:
    return False

  max_size = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for size in range(1, max_size + 1):
    for idxs in itertools.combinations_with_replacement(range(len(digits)), size):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

      replaces = [digits[i][0] for i in idxs]
      replaces.sort(reverse=True)
      uppers = [d for d in replaces if d > base_digit]
      lowers = [d for d in replaces if d < base_digit]

      num = number[:]

      if len(uppers) > 0:
        num = uppers + num[len(uppers):]

      if len(lowers) > 0:
        num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()