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



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Runtime Error

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

#B
"""
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))
"""


#C
"""
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))
"""

#D
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 ans[n] - 1 == ans[n - i]:
            anse += str(a[k])
            n -= i
            break
    if n < 0:
        break
            
print(anse)

Submission status: Runtime Error

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

#B
"""
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))
"""


#C
"""
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))
"""

#D
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 i in range(n + 1)]
num_ans = []
if 5 in a:
    if 3 in a:
        a.remove(3)
    if 2 in a:
        a.remove(2)
if 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 a:
    num_ans.append(num[i])
ans[0] = 0
for i in range(n + 1):
    xmax = 0
    for y, b in enumerate(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 ans[n] - 1 == ans[n - i]:
            anse += str(a[k])
            n -= i
            break
            
print(anse)

Submission status: Runtime Error

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

#B
"""
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))
"""


#C
"""
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))
"""

#D
n,m = map(int, input().split())
a = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = ["" for i in range(n + 1)]
num_ans = []
if 5 in a:
    if 3 in a:
        a.remove(3)
    if 2 in a:
        a.remove(2)
if 3 in a:
    if 2 in a:
        a.remove(2)
if 9 in a:
    if 6 in a:
        a.remove(6)
for i in a:
    num_ans.append(num[i])
for i,k in enumerate(num_ans):
    ans[k] = a[i] 
for i in range(n + 1):
    xmax = 0
    for y, b in enumerate(num_ans):
        if i - b >= 0:
            if ans[i-b] != "":
                x = str(a[y]) + str(ans[i - b])
                xmax = max(xmax, int(x))
    if xmax != 0:
        ans[i] = xmax
print(ans[n])

Submission status: Runtime Error

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

cache = [None]*(n+1)

def f(m):
  if m == 0:
    return 0
  if cache[m] is not None:
    return cache[m]

  b = -1
  for i in a:
    if m >= cost[i]:
      r = f(m-cost[i])
      if r == 0:
        b = max(b, i)
      elif r > 0:
        b = max(b, int(str(i) + str(f(m-cost[i]))))

  cache[m] = b
  return b

print(max(f(n),0))

Submission status: Runtime Error

Solution code:
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])

Submission status: Runtime Error

Solution code:
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])

Submission status: Runtime Error

Solution code:
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 a:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[n])

Submission status: Runtime Error

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


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [-float('inf')] * (N+1)             # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

dp[0] = 0
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 dp[N-cost[Ai]] == digit-1 :
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( int(ans) )

Submission status: Runtime Error

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


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [-float('inf')] * (N+1)             # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

dp[0] = 0
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 dp[N-cost[Ai]] == digit-1 :
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( ans )

Submission status: Runtime Error

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


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [-float('inf')] * (N+1)             # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

dp[0] = 0
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 )


print( dp )

ans = ""
digit = dp[N]

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

print( ans )

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = set()
if 1 in A: S.add(2)
if 7 in A: S.add(3)
if 4 in A: S.add(4)
if 2 in A: S.add(5)
if 3 in A: S.add(5)
if 5 in A: S.add(5)
if 6 in A: S.add(6)
if 9 in A: S.add(6)
if 8 in A: S.add(7)

dp = [[0 for _ in range(N+1)]]
dp[0][0] = 1
while sum(dp[-1]) != 0:
    dp.append([0 for _ in range(N+1)])
    for i in range(N+1):
        for s in S:
            if dp[-2][i] == 1 and i+s <= N:
                dp[-1][i+s] = dp[-2][i]

B = []
for a in sorted(A, reverse=True):
    if a == 9: B.append(('9', 6))
    if a == 8: B.append(('8', 7))
    if a == 7: B.append(('7', 3))
    if a == 6: B.append(('6', 6))
    if a == 5: B.append(('5', 5))
    if a == 4: B.append(('4', 4))
    if a == 3: B.append(('3', 5))
    if a == 2: B.append(('2', 5))
    if a == 1: B.append(('1', 2))

dp = dp[-2::-1]
result = ''
i = N
for d in dp:
    for s, n in B:
        if d[i-n] == 1:
            result += s
            i -= n
            break
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = set()
if 1 in A: S.add(2)
if 7 in A: S.add(3)
if 4 in A: S.add(4)
if 2 in A: S.add(5)
if 3 in A: S.add(5)
if 5 in A: S.add(5)
if 6 in A: S.add(6)
if 9 in A: S.add(6)
if 8 in A: S.add(7)

dp = [[0 for _ in range(N+1)] for _ in range(2)]
dp[0][0] = 1
for s in S:
    if s <= N:
        dp[1][s] = 1
while sum(dp[-1]) != 0:
    dp.append([0 for _ in range(N+1)])
    for i in range(N+1):
        for s in S:
            if dp[-2][i] == 1 and i+s <= N:
                dp[-1][i+s] = dp[-2][i]

B = []
for a in sorted(A, reverse=True):
    if a == 9: B.append(('9', 6))
    if a == 8: B.append(('8', 7))
    if a == 7: B.append(('7', 3))
    if a == 6: B.append(('6', 6))
    if a == 5: B.append(('5', 5))
    if a == 4: B.append(('4', 4))
    if a == 3: B.append(('3', 5))
    if a == 2: B.append(('2', 5))
    if a == 1: B.append(('1', 2))

dp = dp[-2::-1]
result = ''
i = N
for d in dp:
    for s, n in B:
        if d[i-n] == 1:
            result += s
            i -= n
            break
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = set()
if 1 in A: S.add(2)
if 7 in A: S.add(3)
if 4 in A: S.add(4)
if 2 in A: S.add(5)
if 3 in A: S.add(5)
if 5 in A: S.add(5)
if 6 in A: S.add(6)
if 9 in A: S.add(6)
if 8 in A: S.add(7)

dp = [[0 for _ in range(N+1)] for _ in range(2)]
dp[0][0] = 1
for s in S:
    dp[1][s] = 1
while sum(dp[-1]) != 0:
    dp.append([0 for _ in range(N+1)])
    for i in range(N+1):
        for s in S:
            if dp[-2][i] == 1 and i+s <= N:
                dp[-1][i+s] = dp[-2][i]

B = []
for a in sorted(A, reverse=True):
    if a == 9: B.append(('9', 6))
    if a == 8: B.append(('8', 7))
    if a == 7: B.append(('7', 3))
    if a == 6: B.append(('6', 6))
    if a == 5: B.append(('5', 5))
    if a == 4: B.append(('4', 4))
    if a == 3: B.append(('3', 5))
    if a == 2: B.append(('2', 5))
    if a == 1: B.append(('1', 2))

dp = dp[-2::-1]
result = ''
i = N
for d in dp:
    for s, n in B:
        if d[i-n] == 1:
            result += s
            i -= n
            break
print(result)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = set()
if 1 in A: S.add(2)
if 7 in A: S.add(3)
if 4 in A: S.add(4)
if 2 in A: S.add(5)
if 3 in A: S.add(5)
if 5 in A: S.add(5)
if 6 in A: S.add(6)
if 9 in A: S.add(6)
if 8 in A: S.add(7)

dp = [[0 for _ in range(N+1)] for _ in range(2)]
dp[0][0] = 1
for s in S:
    dp[1][s] = 1
while sum(dp[-1]) != 0:
    dp.append([0 for _ in range(N+1)])
    for i in range(N+1):
        for s in S:
            if dp[-2][i] == 1 and i+s <= N:
                dp[-1][i+s] = dp[-2][i]

B = []
for a in sorted(A, reverse=True):
    if a == 9: B.append(('9', 6))
    if a == 8: B.append(('8', 7))
    if a == 7: B.append(('7', 3))
    if a == 6: B.append(('6', 6))
    if a == 5: B.append(('5', 5))
    if a == 4: B.append(('4', 4))
    if a == 3: B.append(('3', 5))
    if a == 2: B.append(('2', 5))
    if a == 1: B.append(('1', 2))

dp = dp[-2::-1]
result = ''
i = N
for d in dp:
    for s, n in B:
        print(s, n)
        if d[i-n] == 1:
            result += s
            i -= n
            break
print(result)

Submission status: Runtime Error

Solution code:
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 >= 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)))

Submission status: Runtime Error

Solution code:
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 = {0: 0}
def dfs(n):
    if n < 0:
        return -float('inf')
    if n not in dp:
        dp[n] = max(dfs(n-c[i]) for i in a) + 1      
    return dp[n]
r = []
while n:
    i = max(a, key=lambda x: dfs(n-c[x]))
    r.append(i)
    n -= c[i]
print(''.join(map(str, r)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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 dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

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

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):
  a_3 = []
  mod_list = []
  
  for i in range(len(a_2)):
    if (a_2[i][1] % a_start[1] not in mod_list) and (a_2[i][1] % a_start[1] != 0):
      a_3.append(a_2[i])
      mod_list.append(a_2[i][1] % a_start[1])
  
  a_3.sort(key=lambda x: x[1], reverse=True)
  if len(a_3) >= 2:
    if a_start[0] + a_3[-1][0] < n and a_3[0][0] < a3[1][0] and a_3[1][0] > a_start[0]:
      a_3.pop(0)

  ans = ""
  while n % a_start[1] != 0:
    for i in range(len(a_3)):
      if n % a_start[1] >= a_3[i][1] % a_start[1]:
        n -= a_3[i][1]
        ans += str(a_3[i][0])
        break
      elif n % a_start[1] == 0:
        break
    else:
      n -= a_3[0][1]
      ans += str(a_3[0][0])
      
  ans = ans + str(a_start[0]) * (n // a_start[1])
  ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
  print(''.join(ans_list))

  
def main():
  N, M = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort(reverse=True)
  num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
  a_list = []
  a_2 = []
  
  for i in range(M):
    if num[a[i]] not in a_list:
      a_2.append([a[i], num[a[i]]])
      a_list.append(num[a[i]])

  a_2.sort(key=lambda x: x[1])
  a_start = a_2.pop(0)
  printing(a_start, a_2, N)
      

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):
  a_3 = []
  mod_list = []
  
  for i in range(len(a_2)):
    if (a_2[i][1] % a_start[1] not in mod_list) and (a_2[i][1] % a_start[1] != 0):
      a_3.append(a_2[i])
      mod_list.append(a_2[i][1] % a_start[1])
  
  a_3.sort(key=lambda x: x[1], reverse=True)
  if len(a_3) >= 2:
    if a_start[0] + a_3[-1][0] < n and a_3[0][0] < a3[1][0] and a_3[1][0] > a_start[0]:
      a_3.pop()

  ans = ""
  while n % a_start[1] != 0:
    for i in range(len(a_3)):
      if n % a_start[1] >= a_3[i][1] % a_start[1]:
        n -= a_3[i][1]
        ans += str(a_3[i][0])
        break
      elif n % a_start[1] == 0:
        break
    else:
      n -= a_3[0][1]
      ans += str(a_3[0][0])
      
  ans = ans + str(a_start[0]) * (n // a_start[1])
  ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
  print(''.join(ans_list))

  
def main():
  N, M = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort(reverse=True)
  num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
  a_list = []
  a_2 = []
  
  for i in range(M):
    if num[a[i]] not in a_list:
      a_2.append([a[i], num[a[i]]])
      a_list.append(num[a[i]])

  a_2.sort(key=lambda x: x[1])
  a_start = a_2.pop(0)
  printing(a_start, a_2, N)
      

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):
  a_3 = []
  mod_list = []
  
  for i in range(len(a_2)):
    if (a_2[i][1] % a_start[1] not in mod_list) and (a_2[i][1] % a_start[1] != 0):
      a_3.append(a_2[i])
      mod_list.append(a_2[i][1] % a_start[1])
  
  a_3.sort(key=lambda x: x[1], reverse=True)
  if len(a_3) >= 2:
    if (a_start[0] + a_3[-1][0] < n) and (a_3[0][0] < a3[1][0]) and (a_3[1][0] > a_start[0]):
      a_3.pop()

  ans = ""
  while n % a_start[1] != 0:
    for i in range(len(a_3)):
      if n % a_start[1] >= a_3[i][1] % a_start[1]:
        n -= a_3[i][1]
        ans += str(a_3[i][0])
        break
      elif n % a_start[1] == 0:
        break
    else:
      n -= a_3[0][1]
      ans += str(a_3[0][0])
      
  ans = ans + str(a_start[0]) * (n // a_start[1])
  ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
  print(''.join(ans_list))

  
def main():
  N, M = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort(reverse=True)
  num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
  a_list = []
  a_2 = []
  
  for i in range(M):
    if num[a[i]] not in a_list:
      a_2.append([a[i], num[a[i]]])
      a_list.append(num[a[i]])

  a_2.sort(key=lambda x: x[1])
  a_start = a_2.pop(0)
  printing(a_start, a_2, N)
      

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)

# xを作るために使うマッチの本数
h = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

# dp[i] = i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
dp = [-1] * (N + 1)
dp[0] = 0

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

digit = dp[N]
ans = ''

n = N
for d in range(digit):
    for a in A:
        if dp[n - h[a]] == digit - 1:
            ans += str(a)
            n -= h[a]
            digit -= 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)

# xを作るために使うマッチの本数
h = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

# dp[i] = i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
dp = [-float('inf')] * (N + 1)
dp[0] = 0

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

digit = dp[N]
ans = ''

n = N
for d in range(digit):
    for a in A:
        if dp[n - h[a]] == digit - 1:
            ans += str(a)
            n -= h[a]
            digit -= 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)

# xを作るために使うマッチの本数
h = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

# dp[i] = i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
dp = [-float('inf')] * (N + 1)
dp[0] = 0

for i in range(N + 1):
    for a in A:
        #if i - h[a] < 0: continue
        dp[i] = max(dp[i-h[a]] + 1, dp[i])


digit = dp[N]
ans = ''

n = N
for d in range(digit):
    for a in A:
        if dp[n - h[a]] == digit - 1:
            ans += str(a)
            n -= h[a]
            digit -= 1
            break
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
dp = [0]
cost = [0,2,5,5,4,5,6,3,7,6]
for i in range(1, N+1):
    dp.append(-(2<<10))
    for a in A:
        if i >= cost[a]: 
            dp[i] = max(dp[i - cost[a]] + 1, dp[i])
ans = ""
while N > 0:
    for e in A:
        if dp[N] - 1 == dp[N - cost[e]]:
            if dp[N] == 1:
                if N != cost[e]: continue
            N -= cost[e]
            ans += str(e)
            break
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
dp = [0, -int('inf')]
cost = [0,2,5,5,4,5,6,3,7,6]
for i in range(2, N+1):
    dp.append(-int('inf'))
    for a in A:
        if i >= cost[a]: 
            dp[i] = max(dp[i - cost[a]] + 1, dp[i])
ans = ""
while N > 0:
    for e in A:
        if dp[N] - 1 == dp[N - cost[e]]:
            if dp[N] == 1:
                if N != cost[e]: continue
            N -= cost[e]
            ans += str(e)
            break
print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <string>
#include <functional>
using namespace std;
using ll = long long;

int N, M;
int dp[10001] = {};
vector<ll> A;
ll cost[] = {0,2,5,5,4,5,6,3,7,6};
string ans = "";
int tmp;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;

    for (int m = 0; m < M; ++m) {
        cin >> tmp;
        A.push_back(tmp);  
    }
    sort(A.begin(), A.end(), greater<int>());

    for (int n = 2; n <= N; ++n) {
        for (auto e : A) {
            if (n >= cost[e])
                dp[n] = max(dp[n], dp[n - cost[e]] + 1);
        }
    }

    int remained = N;
    while (remained > 0) {
        for (auto e : A) {
            if (dp[remained - cost[e]] == dp[remained] - 1) {
                if (remained < cost[e]) continue;
                if (1 == dp[remained])
                    if (remained != cost[e]) continue;
                ans += to_string(e); 
                remained -= cost[e]; 
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
dp = [0, 0]
cost = [0,2,5,5,4,5,6,3,7,6]
for i in range(2, N+1):
    dp.append(0)
    for a in A:
        if i >= cost[a]: 
            dp[i] = max(dp[i - cost[a]] + 1, dp[i])
ans = ""
while N > 0:
    for e in A:
        if dp[N] - 1 == dp[N - cost[e]]:
            if dp[N] == 1:
                if N != cost[e]: continue
            N -= cost[e]
            ans += str(e)
            break
print(ans)

Submission status: Runtime Error

Solution code:
def search(N, idx):
    global a, M, count

    if N == 0:
        return True
    elif N < 0:
        return False
    elif idx == M:
        return False

    loop = N // a[idx][0]
    for i in range(loop, -1, -1):
        flag = search(N-a[idx][0]*i, idx+1)
        if flag:
            if i:
                count.append([a[idx][1], i])
            return True

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

if 6 in A and 9 in A:
    A.remove(6)

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

x = [2,5,5,4,5,6,3,7,6]
a = [[x[A[i]-1],i] for i in range(len(A))]
count = []
a.sort()

search(N, 0)

nums = [[A[count[i][0]], count[i][1]] for i in range(len(count))]

nums.sort(reverse=True)

for i in range(len(nums)):
    print(str(nums[i][0]) * nums[i][1], end='')

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)


    if a_start[0] + a_3[-1][0] < n and len(a_3) >= 2:
        if a_3[0][0] < a_3[1][0] and a_3[1][0] > a_start[0]:
            a_3.pop(0)


    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
            elif n % a_start[1] == 0:
                break
        else:
            n -= a_3[0][1]
            ans += str(a_3[0][0])

    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Runtime Error

Solution code:
from collections import Counter


def parse_line(line, type=int):
    return [type(x) for x in line.split(' ')]


#              1, 2, 3, 4, 5, 6, 7, 8, 9
weight = ['x', 2, 5, 5, 4, 5, 6, 3, 7, 6]


def run(k, weight_to_num, cache):
    if k not in cache:
        if k <= 1:
            res = 0
        else:
            res = 0
            for w, num in weight_to_num.items():
                res = max(res, run(k - w, weight_to_num, cache))
            if res > 0:
                res += 1
            if k in weight_to_num:
                res = max(1, res)
        cache[k] = res
    return cache[k]


def main():
    n, m = parse_line(input())
    numbers = set(parse_line(input()))
    #numbers = [6, 8, 9]

    #for n in range(2, 60):

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

    weight_to_num = {weight[v]: v for v in numbers}
    cache = {}
    run(n, weight_to_num, cache)
    #print(cache)
    #return

    ws = list(weight_to_num.keys())
    ws.sort(reverse=True, key=lambda w: weight_to_num[w])
    res = []
    cache = {k:v for k,v in cache.items() if v > 0}
    cache[0] = 0

    if n not in cache:
        return

    l = cache[n]
    while l:
        for w in ws:
            if cache.get(n - w, 'False') == l - 1:
                res.append(weight_to_num[w])
                n = n - w
                l -= 1
                break
    print(''.join((str(x) for x in res)))


if __name__ == '__main__':
    main()

# 20 4
# 3 7 8 4

Submission status: Runtime Error

Solution code:
from collections import Counter


def parse_line(line, type=int):
    return [type(x) for x in line.split(' ')]


#              1, 2, 3, 4, 5, 6, 7, 8, 9
weight = ['x', 2, 5, 5, 4, 5, 6, 3, 7, 6]


def run(k, weight_to_num, cache):
    if k not in cache:
        if k <= 1:
            res = 0
        else:
            res = 0
            for w, num in weight_to_num.items():
                res = max(res, run(k - w, weight_to_num, cache))
            if res > 0:
                res += 1
            if k in weight_to_num:
                res = max(1, res)
        cache[k] = res
    return cache[k]


def main():
    n, m = parse_line(input())
    numbers = set(parse_line(input()))
    if 6 in numbers and 9 in numbers:
        numbers.remove(6)
    if 2 in numbers and 3 in numbers:
        numbers.remove(2)
    if 2 in numbers and 5 in numbers:
        numbers.remove(2)
    if 3 in numbers and 5 in numbers:
        numbers.remove(3)

    weight_to_num = {weight[v]: v for v in numbers}
    cache = {}
    run(n, weight_to_num, cache)
    #print(cache)
    #return

    ws = list(weight_to_num.keys())
    ws.sort(reverse=True, key=lambda w: weight_to_num[w])
    res = []
    cache = {k:v for k,v in cache.items() if v > 0}
    cache[0] = 0

    l = cache[n]
    while l:
        for w in ws:
            if cache.get(n - w, 'False') == l - 1:
                res.append(weight_to_num[w])
                n = n - w
                l -= 1
                break
    print(''.join((str(x) for x in res)))


if __name__ == '__main__':
    main()

# 20 4
# 3 7 8 4

Submission status: Runtime Error

Solution code:

# coding: utf-8

# In[46]:


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]
    
    result = [-1 for _ in range(N+1)]
    result[0] = 0
    
    print(result)
    
    for i in range(1, N+1):
        for a in A:
            if i < match[a]:
                print(i,a,result)
                continue
            result[i] = max(result[i], result[i-match[a]]*10+a)
            print(i,a,result)
    
    print(result[N])


# In[47]:


main()

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
for _ in range(10**5):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
    dim -= 1
    if dim <= 0:
        break
print(ans if ans else 0)

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
for _ in range(INF):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
    dim -= 1
    if dim <= 0:
        break
print(ans if ans else 0)

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
while(dim > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
    dim -= 1
    if dim <= 0:
        break
print(ans if ans else 0)

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
while(dim > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
    dim -= 1
    if dim == 0:
        break
print(ans if ans else 0)