Problem:
 Score : 400 points    Problem Statement Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:   Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9) .  The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6 , respectively.       Constraints  All values in input are integers.  2 \leq N \leq 10^4  1 \leq M \leq 9  1 \leq A_i \leq 9  A_i are all different.  There exists an integer that can be formed by exactly N matchsticks under the conditions.         Input Input is given from Standard Input in the following format:  N  M  A_1  A_2  ...  A_M       Output Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.        Sample Input 1 20 4
3 7 8 4      Sample Output 1 777773  The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.       Sample Input 2 101 9
9 8 7 6 5 4 3 2 1      Sample Output 2 71111111111111111111111111111111111111111111111111  The output may not fit into a 64 -bit integer type.       Sample Input 3 15 3
5 4 6      Sample Output 3 654

Solution (Python):
N, M = map(int, raw_input().split())
A = map(int, raw_input().split())
all_cost = [-10**15, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-10**15] * (N+1)

dp[0] = 0
for i in range(1, N+1, 1):
    max_val = -10**15
    for a in A:
        if i - all_cost[a] >= 0 and dp[i - all_cost[a]] != -10**15:
            val = dp[i - all_cost[a]] + 1
            if val > max_val: max_val = val
    dp[i] = max_val

A.sort(reverse=True)

result = ''
idx = N
while idx > 0:
    for a in A:
        if idx - all_cost[a] < 0: continue
        if dp[idx - all_cost[a]] == dp[idx] - 1:
            result += str(a)
            idx -= all_cost[a]
            break

print result

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(2*10**5)


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

INF = 10**15

C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)



@lru_cache(maxsize=None)
def dfs(n):
    return (
        [-INF for _ in range(9)] if n < 0 else
        [0 for _ in range(9)] if n == 0 else
        max(
            (
                [
                    t + 1 if i == a else t
                    for i, t in enumerate(dfs(n - C[a]), start=1)
                ]
                for a in A
            ),
            key=lambda x: [sum(x)] + list(reversed(x))
        )
    )



ans = ''.join(str(a) * dfs(N)[a - 1] for a in sorted(A, reverse=True))
print(ans)

Solution (Python):
nn=[2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
a=input().split()
b=[]
for i in range(m):
  a[i]=int(a[i])
  
if 5 in a:
  if 2 in a:
    a.remove(2)
  if 3 in a:
    a.remove(3)
elif 3 in a:
  if 2 in a:
    a.remove(2)
if 9 in a:
  if 6 in a:
    a.remove(6)
    
a.sort(reverse=True)
for i in range(len(a)):
  b.append(nn[a[i]-1])
  
dp=[-10*18 for _ in range(n+1)]
dp[0]=0
for i in range(n):
  for j in range(len(b)):
    if i+b[j]>n:
      continue
    dp[i+b[j]]=max(dp[i+b[j]],dp[i]+1)
    
k=dp[n]
ans=""
for i in range(k):
  for j in range(len(b)):
    if n-b[j]<0:
      continue
    if dp[n-b[j]]==dp[n]-1:
      ans+=str(a[j])
      n-=b[j]
      break
      
print(ans)

Solution (Python):
INF = 10 ** 6

def num(k):
    if k == 1:
        return 2
    elif k == 7:
        return 3
    elif k == 4:
        return 4
    elif k == 2 or k == 3 or k == 5:
        return 5
    elif k == 6 or k == 9:
        return 6
    elif k == 8:
        return 7

n, m = map(int,input().split())
l = list(map(int,input().split()))
l.sort(reverse = True)
         
dp = [(-1) * INF] * (n+1)

dp[0] = 0

for i in range(2,n+1):
    can = []
    for x in l:
        if i-num(x)>=0:
            can.append(dp[i-num(x)]+1)
    if can == []:
        dp[i] = (-1) * INF
    else:
        dp[i] = max(can)
        


anslist = [0] * dp[n]

left = n

for j in range(dp[n],0,-1):
    if j == 1:
        for x in l:
            if num(x) == left:
                anslist[j-1] = x
                break
    else:
        for x in l:
            if dp[left-num(x)] == j - 1:
                anslist[j-1] = x
                left = left-num(x)
                break
            
    

            
            
ans = 0

for j in range(0,dp[n]):
    ans = ans + anslist[j] * (10 ** j)

print(ans)

Solution (Python):
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
x,y,inf = [2,5,5,4,5,6,3,7,6],set(),float("inf")
dp,ans = [0,-inf],[]
def f(i,y):
    num = -inf
    for j in y:
        if i>=j: num = max(num,dp[i-j]+1)
    return num 
for i in a: y.add(x[i-1])
for i in range(2,n+1): dp.append(f(i,y))
a,N = sorted(a)[::-1],n
for i in range(dp[n]):
    for j in a:
        if N>=x[j-1] and dp[N-x[j-1]]==dp[N]-1:
            ans.append(str(j))
            N-=x[j-1]
            break
print("".join(ans))

Solution (Python):
n, m = map(int, input().split())
alist = list(sorted(map(int, input().split())))[::-1]
md = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

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

for i in range(n+1):
  for a in alist:
    if i - md[a] >= 0:
      if dp[i] < dp[i - md[a]] + 1:
        dp[i] = dp[i - md[a]] + 1

ans = ''
res = n
while i > 0:
  for a in alist:
    if i >= md[a] and dp[i]-1 == dp[i-md[a]]:
      ans += str(a)
      i -= md[a]
      break

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

nums = {}
nums[1] = 2
nums[2] = 5
nums[3] = 5
nums[4] = 4
nums[5] = 5
nums[6] = 6
nums[7] = 3
nums[8] = 7
nums[9] = 6

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

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

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

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

cost = sorted(list(zip([[2, 5, 5, 4, 5, 6, 3, 7, 6][a-1] for a in A], A)), key=lambda x: (x[0], -x[1]))


tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key=lambda x:-x[1])


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

n = N
out = ""
i = 0
while n:
    c, a = cost[i]
    if (n >= c) and (dp[n-c] == dp[n] - 1):
        n -= c
        out += str(a)
    else:
        i += 1
print(out)

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

cost = sorted(list(zip([[2,5,5,4,5,6,3,7,6][a-1] for a in A],A)),key = lambda x: (x[0],-x[1]))


tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key = lambda x:-x[1])

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

n = N
out = ""
i = 0
while n:
    c , a = cost[i]
    if (n>=c) and (dp[n-c] == dp[n]-1):
        n -= c
        out += str(a)
    else:
        i+=1
print(out)

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
match=[0,2,5,5,4,5,6,3,7,6]
make=dict()
for a in A:
    make[a]=match[a]
dp=[-1]*(N+1)
dp[0]=0
for k in range(1,1+N):
    for d,m in make.items():
        if k-m<0 or dp[k-m]==-1:continue
        dp[k]=max(dp[k],dp[k-m]+1)
        
ans=''
now=N
for k in range(dp[N]):
    res=(0,0)
    for d,m in make.items():
        if now-m<0:continue
        if dp[now-m]+1==dp[now] and res[0]<d:
            res=(d,m)
    ans+=str(res[0])
    now-=res[1]
print(int(ans))

Solution (Python):
match, _ = [int(item) for item in input().split()]
kind = sorted([int(item) for item in input().split()])

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

dp = [-1] * int(match + 1)

dp[0] = 0
for i in range (match + 1):
  for k in kind:
    if i < use[k]:
      continue
    dp[i] = max(dp[i], dp[i - use[k]] * 10 + k)
    
print(dp[match])

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

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


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

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

n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

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


dpi = [-1<<50] * 9 + [0]
def dp(i):
    '''i should be started from 1'''

    ans = []
    for j in a:
        ans.append(dpi[len(dpi) - key[j]] + 1)
    dpi.append(max(ans))

    if i == n:
        return dpi[len(dpi) - 1]
    else:
        return dp(i + 1)

i = dp(1)
a.sort()

s = ''
cur = -1
for j in range(i):
    for k in reversed(a):
        if dpi[cur-key[k]] == dpi[cur] - 1:
            s += str(k)
            cur -= key[k] 
            break
        else:
            continue

print(int(s))

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

dp = [None] * (N + 10)
dp[0] = ""
for i in range(N):
    if dp[i] == None:
        continue
    for k in numbers:
        idx = i + cost[k - 1]
        s1 = dp[i] + str(k)
        s2 = dp[idx]

        if s2 == None or len(s1) > len(s2):
            dp[idx] = s1
        elif len(s1) == len(s2) and s1 > s2:
            dp[idx] = s1
print(dp[N])

Solution (Python):
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = {}
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

dp = ["-" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
    
dp[0] = ""
for i in range(length + 1):
    if dp[i] != "-":
        for m in match:
            dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Solution (Python):
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = {}
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

dp = ["-" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
    


dp[0] = ""
for i in range(length + 1):
    
    if dp[i] != "-":
        for m in match:
            
            dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Solution (Python):
num_A = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = ""
while remain_match > 0:
    for Ai in A:
        if remain_match >= num_A[Ai] and dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans))

Solution (Python):
num_A = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = "0"
while remain_match > 0:
    for Ai in A:
        if remain_match >= num_A[Ai] and dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans[1:]))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
 
ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000
 
def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0
 
	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)
 
	memo[num] = ret
	return ret
 
ma.sort()
print(dfs(N))

Solution (Python):
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max(n-200, 0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 50 < i < n-50:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
ans = ans[:10] + str(r[0])*k + ans[10:]
print(ans)

Solution (Python):
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 42 < i < n-42:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
print(ans)

Solution (Python):
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
_max = [0] + [-INF]*n
for i in range(1, n+1):
  for x in l:
    ind = i-x[1]
    if ind >= 0:
      _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
print(ans)

Solution (Python):
__MATCH = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6, ]
__INF = float('inf')


def match_matching(N: int, M: int, A: list) -> int:
    
    dp = [-__INF] * (N+1)
    dp[0] = 0
    for i in range(1, N+1):
        dp[i] = max([-__INF] +
                    [dp[i - __MATCH[a]] for a in A if i >= __MATCH[a]]) + 1

    
    _A = sorted(A, reverse=True)
    used_matches = 0
    ans = 0
    for n in range(dp[N], 0, -1):
        for a in _A:
            used_matches += __MATCH[a]
            if used_matches <= N and dp[N-used_matches] == n - 1:
                ans = ans * 10 + a
                break
            used_matches -= __MATCH[a]

    return ans


if __name__ == "__main__":
    N, M = [int(s) for s in input().split()]
    A = [int(s) for s in input().split()]

    ans = match_matching(N, M, A)

    print(ans)

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


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

cost = []
for i in range(M):
    cost.append([A[i], match[A[i]]])

dp[0] = 0


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


tmp = 0 
res = ''
cost.sort(key=lambda x: x[0], reverse=True) 

for i in range(dp[N]):
    for j in range(M):
        if N - cost[j][1] - tmp >= 0: 
            if dp[N - cost[j][1] - tmp] == dp[N - tmp] - 1:
                '''
                左辺:まだ残っているマッチ本数から対象の整数を利用した場合の桁数
                右辺:まだ残っているマッチで実現できる桁数-1
                '''
                res = res + str(cost[j][0])
                tmp += cost[j][1]
                break 
            
print(res)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
 
ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000
 
def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0
 
	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)
 
	memo[num] = ret
	return ret
 
ma.sort()
print(dfs(N))

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

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

ma.sort()
print(dfs(N))

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

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			d = dfs(num - ma_map[p])
			if d == -1: continue
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

ma.sort()
print("{}".format(dfs(N)))

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

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

cost = []
for i in range(M):
    cost.append([A[i], match[A[i]]])

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

tmp = 0 
res = ''
cost.sort(key=lambda x: x[0], reverse=True)
for i in range(dp[N]):
    for j in range(M):
        if N - cost[j][1] - tmp >= 0:
            if dp[N - cost[j][1] - tmp] == dp[N - tmp] - 1:
                res = res + str(cost[j][0])
                tmp += cost[j][1]
                break
            
print(res)

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

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

for i in range(1, n+1):
    for a_j in a:
        i_prev = i - n_use[a_j]
        if i_prev < 0:
            continue
        else:
            dp[i] = max(dp[i], dp[i_prev]*10+a_j)

print(dp[-1])

Solution (Python):
m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] + [-N] * N
for x in range(1, N + 1):
    mx = -N
    for j in range(M):
        num = x - m[A[j]]
        if num >= 0:
            if mx < dp[num] + 1:
                mx = dp[num] + 1
    if mx < 0:
        dp[x] = -N
    else:
        dp[x] = mx

A.sort(reverse=True)
nd = dp[N]
n = N
for i in range(N):
    for a in A:
        if n >= m[a] and dp[n - m[a]] == nd - 1:
            nd -= 1
            n -= m[a]
            print(a, end="")
            break
print()

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


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

cost =[0, 2,5,5,4,5,6,3,7,6]
for i in range(N+1):
    for a in A:
      
       new_i = i + cost[a]
       if new_i <= N:
        dp[new_i] = max([dp[new_i],  dp[i]+1])

sa = sorted(A, reverse=True)
n = N
ans = 0
while n > 0:
  for a in sa:
    nn = n-cost[a]
    if nn >= 0 and dp[n] == dp[nn] +1:
      ans = ans * 10 + a
      n -= cost[a]
      break

print(ans)

Solution (Python):
n, m = map(int, input().split())
INF = 10 ** 6
match_dict = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5,
              6: 6, 7: 3, 8: 7, 9: 6}

a_list = list(map(int, input().split()))
a_sorted = sorted(a_list, reverse=True)

dp = [0, -INF]

for i in range(2, n + 1):
    tmp_dp = []
    for a in a_sorted:
        if i - match_dict[a] < 0:
            tmp_dp.append(-INF)
        else:
            tmp_dp.append(dp[i - match_dict[a]] + 1)
    dp.append(max(tmp_dp))

sum_str = ''
tmp_i = n
while tmp_i > 0:
    for a in a_sorted:
        if tmp_i >= match_dict[a] and dp[tmp_i - match_dict[a]] == dp[tmp_i] - 1:
            sum_str = sum_str + str(a)
            tmp_i = tmp_i - match_dict[a]
            break

print(int(sum_str))

Solution (Python):
from operator import itemgetter

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

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

c = []

for x in a:
    if x in [1, 4, 7, 8]:
        c.append((x, b[x - 1]))

if 5 in a:
    c.append((5, 5))
elif 3 in a:
    c.append((3, 5))
elif 2 in a:
    c.append((2, 5))

if 9 in a:
    c.append((9, 6))
elif 6 in a:
    c.append((6, 6))

c = sorted(c, key=itemgetter(1), reverse=True)

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

for i in range(2, n + 1):
    for x, y in c:
        if i >= y:
            dp[i] = max(dp[i], dp[i - y] + 1)
    

c = sorted(c, key=itemgetter(0), reverse=True)




s = []
k = dp[n]
while k > 0:
    
    
    for x, y in c:
        if n >= y:
            if dp[n - y] == k - 1:
                s.append(str(x))
                k -= 1
                n -= y
                break

print(int(''.join(s)))

Solution (Python):
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

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

tmp_n = n
ans =""
for i in range(dp[n]):
    for j in range(m):
        if i==dp[n]-1 and tmp_n- c[am[j]-1] != 0:
            continue
        if tmp_n - c[am[j]-1] >= 0 and dp[tmp_n - c[am[j]-1]] == dp[tmp_n] -1:
            ans+=(str(am[j]))
            tmp_n -= c[am[j]-1]
            break


print(ans)

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
INF = 10**5
COST = [INF,2,5,5,4,5,6,3,7,6]
digit = [-INF]*(N+1)
digit[0] = 0
for i in range(1, N+1):
    for a in A:
        c = COST[a]
        if i - c < 0:
            continue
        digit[i] = max(digit[i], 1 + digit[i-c])
ans = ''
n = N
for i in range(digit[N], 0, -1):
    for a in A:
        new_n = n - COST[a]
        if new_n < 0 or digit[new_n] < i - 1:
            continue
        ans += str(a)
        n = new_n
        break
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def num(key):
    if key == 1:
        return 2
    elif key == 7:
        return 3
    elif key == 4:
        return 4
    elif key == 9 or key == 6:
        return 6
    elif key == 8:
        return 7
    else:
        return 5

N, M, = readline().split()
N = int(N)
M = int(M)
A = list(map(int, readline().split()))
A.sort(reverse = True)
dp = [-float('inf'),] *(N+1)
dp[0] = 0
for i in range(1, N+1):
    temp = []
    for j in range(M):
        if i - num(A[j]) >= 0:
            temp.append(dp[i-num(A[j])] + 1)
    if len(temp) > 0:
        dp[i] = max(temp)

digit = dp[N]
ans = []
for i in range(digit):
    for j in range(M):
        if N - num(A[j]) >= 0 and dp[N-num(A[j])] == dp[N] - 1:
            ans.append(A[j])
            N = N - num(A[j])
            break
for i in range(digit):
    write(str(ans[i]))
write("\n")

Solution (Python):
N,M=map(int,input().split())
A=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 A:
        if i+weight[a]<N+1:
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)
print(dp[N])

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

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


def f(n,al):
    INF = 10**18
    dp = [-INF for _ in range(n+1)]
    dp[0] = 0

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

    res = []
    al.sort(reverse=True)

    while n>0:
        for a in al:
            if n-num[a]>=0 and dp[n-num[a]]==dp[n]-1:
                res.append(str(a))
                n -= num[a]
                break

    return "".join(res)

if __name__ == '__main__':
    n,m = map(int, input().split())
    al = list(map(int, input().split()))
    print(f(n,al))

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):
n,m=map(int, input().split())
value=sorted(list(map(int,input().split())), reverse=True)
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 j in value:
        if i + weight[j] < n+1:
            dp[i+weight[j]] = max(dp[i+weight[j]],dp[i]*10+j)
print(dp[n])

Solution (Python):
inf = float("inf")
N, M = map(int, input().split())
A = map(int, input().split())
C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = {m: C[m - 1] for m in A}
dp = [0]
for i in range(1, N + 1):
    dp.append(
        max([dp[i - c] if i - c >= 0 else -inf for c in costs.values()]) + 1)

digits = list(costs.keys())
digits = sorted(digits, reverse=True)
num = N
result = []
for _ in range(dp[N]):
    for digit in digits:
        if num >= costs[digit] and dp[num - costs[digit]] != -inf and dp[num - costs[digit]] == dp[num] - 1:
            result.append(str(digit))
            num -= costs[digit]
            break
print("".join(result))

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 = [int(x) for x in input().split()]
a = sorted([int(x) for x in input().split()])
INF = 10**9

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

keta = [-INF for _ in range(N+1)]
keta[0] = 0
for i in range(1, N+1):
    cand = [keta[i-num[aa]] for aa in a if i-num[aa] >= 0]
    if len(cand) > 0:
        keta[i] = max(cand) + 1

n = N
ans = ""
while n > 0:
    cand = [aa for aa in a if n-num[aa] >= 0 and keta[n]-1 == keta[n-num[aa]]]
    if len(cand) > 0:
        ans += str(cand[-1])    
        n = n - num[cand[-1]]
print(ans)

Solution (Python):
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  if i[0] - 1 < N:
    dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        dp[k] = t
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            dp[k] = t
            break
          elif t[ii] < dp[k][ii]:
            break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for j in range(t[i]):
    Ans += str(i)
    
print(Ans)

Solution (Python):
from fractions import *
from collections import *
n, m = map(int,input().split())
a = sorted(map(int,input().split()))[::-1]
c = [0,2,5,5,4,5,6,3,7,6]
mi = min(a, key=lambda x: c[x])
x = sum(c[i]*c[mi]//gcd(c[i],c[mi]) for i in a if i!=mi)
q, r = divmod(max(0, n-x), c[mi])
n = min(n, x+r)
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)
d = Counter()
d[mi] += q
while n:
    i = max((i for i in a if n>=c[i]), key=lambda x: dp[n-c[x]])
    d[i] += 1
    n -= c[i]
print(''.join(str(k)*d[k] for k in sorted(d)[::-1]))

Solution (Python):
n,m=map(int, input().split())
value=sorted(list(map(int,input().split())))[::-1]
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 j in value:
        if i + weight[j] < n+1:
            dp[i+weight[j]] = max(dp[i+weight[j]],dp[i]*10+j)
print(dp[n])

Solution (Python):
INF = float('inf')

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

num = [N + 1, 2, 5, 5, 4, 5, 6, 3, 7, 6]



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



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

a = list(sorted(a, reverse=True))


need = dp[N]


rest = N


ans = ''

while need > 0:
    for aa in a:
        
        idx = rest - num[aa]
        if idx >= 0:
            
            if dp[idx] == need - 1:
                ans += str(aa)
                

                rest -= num[aa]
                need -= 1

                break
                
print(ans)

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

Solution (Python):

import math
def inpul(): return list(map(int, input().split()))

N, M = inpul()
A = inpul()

c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010

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

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

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

d = [-1]*(10*N)
d[0] = 0

for i in range(1, N+1):
    for A in A_arr:
        d[i] = max(d[i], d[i-B_arr[A]]*10+A)

print(d[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):

n,m,*a=map(int,open(0).read().split())



"""
d: [マッチ棒が0の時は0,
    
"""
d=[0]+[-1]*n*9


for i in range(1,n+1):
    
    
    
    d[i]=max(j + d[i-int('0255456376'[j])]*10 for j in a)
print(d[n])