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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = LIST()
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]
arr = [[1, 2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
arr2 = []
for i in range(9):
    if arr[i][0] in a:
        arr2.append(arr[i])
arr2.sort(key=lambda x:x[1])
#print('arr2', arr2)
larr2 = len(arr2)
ans = []
arr3 = []
arr4 = []
for i in range(larr2):
    for j in range(i + 1, larr2):
        if not arr2[i][1] + arr2[j][1] in arr3:
            arr3.append(arr2[i][1] + arr2[j][1])
            arr4.append([arr2[i][0], arr2[j][0]])
        else:
            index = arr3.index(arr2[i][1] + arr2[j][1])
            arr4[index].sort(reverse=True)
            t = sorted([arr2[i][0], arr2[j][0]], reverse=True)
            flag = False
            if a[0] > arr4[index][0] or (a[0] == arr4[index][0] and t[1] > arr4[index][1]):
                arr4[index] = t
#print('arr3', arr3)
#print('arr4', arr4)
maxarr3 = max(arr3)
ii = 0
while n > 0:
    if n in arr3 and not n - arr2[ii][1] in arr3:
        index = arr3.index(n)
        ans.append(arr4[index][0])
        ans.append(arr4[index][1])
        n = 0
    elif ii >= 0:
        n -= arr2[ii][1]
        ans.append(arr2[ii][0])
    elif n < maxarr3 or ii < 0:
        index = arr2.index([ans[len(ans) - 1], b[ans[len(ans) - 1] - 1]])
        n += arr2[index][1]
        del ans[len(ans) - 1]
        ii = index + 1
        if ii >= larr2:
            ii = -1
    #print(n)
    
#print('ans', ans)
ans.sort(reverse=True)
anstr = ''
for i in range(len(ans)):
    anstr += str(ans[i])
print(anstr)
'''
for i in range(len(arr2)):
    l = n // arr2[i][1] #同じ数字の桁数
    m = n % arr2[i][1] #端数
    print(l, m)
    if m != 0:
        while 
        indexes = []
        for j in range(len(arr2)):
            if m == arr2[j][1]:
                indexes.append(j)
        print(indexes)
        index = -1
        mx = 0
        for j in indexes:
            if mx < arr2[j][0]:
                mx = arr2[j][0]
                index = j
        if index >= 0:
            if arr2[index][0] > arr2[i][0]:
                ans = str(arr2[index][0]) + str(arr2[i][0]) * l
                print('a')
                print(ans)
                exit()
            else:
                ans = str(arr2[i][0]) * l + str(arr2[index][0])
                print('b')
                print(ans)
                exit()
    elif m == 0:
        ans = str(arr2[index][0]) * l
        print('c')
        print(ans)
        exit()
'''

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[[] for i in range(0,10)]
for i in range(0,M):
    if 1 in A:
        B[2].append(1)
    if 2 in A:
        B[5].append(2)
    if 3 in A:
        B[5].append(3)
    if 4 in A:
        B[4].append(4)
    if 5 in A:
        B[5].append(5)
    if 6 in A:
        B[6].append(6)
    if 7 in A:
        B[3].append(7)
    if 8 in A:
        B[7].append(8)
    if 9 in A:
        B[6].append(9)


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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[[] for i in range(0,10)]
for i in range(0,M):
    if 1 in A:
        B[2].append(1)
    if 2 in A:
        B[5].append(2)
    if 3 in A:
        B[5].append(3)
    if 4 in A:
        B[4].append(4)
    if 5 in A:
        B[5].append(5)
    if 6 in A:
        B[6].append(6)
    if 7 in A:
        B[3].append(7)
    if 8 in A:
        B[7].append(8)
    if 9 in A:
        B[6].append(9)


dp=['n' for i in range(0,N+1)]
if 1 in A:
    dp[2]=1
if 2 in A:
    dp[5]=2
if 3 in A:
    dp[5]=3
if 4 in A:
    dp[4]=4
if 5 in A:
    dp[5]=5
if 6 in A:
    dp[6]=6
if 7 in A:
    dp[3]=7
if 8 in A:
    dp[7]=8
if 9 in A:
    dp[6]=9
for i in range(4,N+1):
    if i==4:
        if B[2]!=[]:
            dp[4]=11
    if i==5:
        if B[3]!=[] and dp[2]!='n':
            dp[5]=71
    if i==6:
        a=0
        b=0
        c=0
        if B[2]!=[] and dp[4]!='n':
            a=1*10**len(str(dp[4]))+dp[4]
        if B[3]!=[]:
            b=77
        if B[4]!=[] and dp[2]!='n':
            c=41
        if dp[6]=='n':
            x=max(a,b,c)
            if x!=0:
                dp[6]=x
        else:
            dp[6]=max(a,b,c,dp[6])
    if i==7:
        a=0
        b=0
        c=0
        d=0
        if B[2]!=[] and dp[5]!='n':
            a=1*10**len(str(dp[5]))+dp[5]
        if B[3]!=[] and dp[4]!='n':
            b=7*10**len(str(dp[4]))+dp[4]
        if B[4]!=[] and dp[3]!='n':
            c=47
        if B[5]!=[] and dp[2]!='n':
            d=max(B[5])*10+1
        if dp[7]=='n':
            x=max(a,b,c,d)
            if x!=0:
                dp[7]=x
        else:
            dp[7]=max(dp[7],a,b,c,d)
    if i>7:
        a=0
        b=0
        c=0
        d=0
        e=0
        f=0
        if B[2]!=[] and dp[i-2]!='n':
            a=1*10**(len(str(dp[i-2])))+dp[i-2]
        if B[3]!=[] and dp[i-3]!='n':
            b=7*10**(len(str(dp[i-3])))+dp[i-3]
        if B[4]!=[] and dp[i-4]!='n':
            c=4*10**(len(str(dp[i-4])))+dp[i-4]
        if B[5]!=[] and dp[i-5]!='n':
            d=max(B[5])*10**(len(str(dp[i-5])))+dp[i-5]
        if B[6]!=[] and dp[i-6]!='n':
            e=max(B[6])*10**(len(str(dp[i-6])))+dp[i-6]
        if B[7]!=[] and dp[i-7]!='n':
            f=8*10**(len(str(dp[i-7])))+dp[i-7]
        x=max(a,b,c,d,e,f)
        if x==0:
            dp[i]='n'
        else:
            dp[i]=x
print(dp[N])

Submission status: Runtime Error

Solution code:
def main():
    nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    As = {}
    for a in A:
        As[nums[a]] = max(a, As.get(nums[a], 0))
    A = sorted(list(As.values()), key=lambda x: nums[x])
    def helper(n, A):
        if n == 0:
            return []
        if n < 0:
            return None
        for i in A:
            s = helper(n - nums[i], A)
            if s is None:
                continue
            return s + [i]
        return None
            
    print(''.join(str(i) for i in sorted(helper(N, A), reverse=True)))

main()

Submission status: Runtime Error

Solution code:
def solve():
  N,M = map(int, input().split())
  A = list(map(int, input().split()))
  A.sort(reverse=True)
  w = [required_match[a] for a in A]
  # print(A,w)
  dp = [[0 for _ in range(N+1)] for _ in range(M+1)]
  for i in range(0, M):
    for j in range(1, N+1):
      if j < w[i]:
        dp[i+1][j] = dp[i][j]
      elif j-w[i] == 0 or dp[i+1][j-w[i]] >= 1:
        dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+1) # 後ろにつけたら自動で辞書順にされてる
      else:
        dp[i+1][j] = dp[i][j]
  
  # print(dp)
  # print(dp[M][N])
  # DPテーブルの右側でdp[M][N]になっているものを分解して、最大のものを選ぶ  高々9*N回で終わる
  start_M = M
  candidate = []
  while dp[start_M][N] == dp[M][N]: 
    # O(9)
    m = start_M
    n = N
    ret = ''
    while n > 0:
      # 左に移動する
      if n - w[m-1] < 0:
        break
      if dp[m][n] == dp[m][n-w[m-1]]+1:
        ret = str(A[m-1])+ret
        n = n-w[m-1]
      else:
        break
      
      # 上に移動する
      while m >= 1 and dp[m][n] == dp[m-1][n]:
        m -= 1

      # print(dp[m][n], dp[m-1][n])
      # print(m, n, ret)

    if n == 0:
      candidate.append(ret)

    start_M -= 1
  # print(candidate)
  print(max(candidate))
  
solve()

Submission status: Runtime Error

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

# 使うマッチ棒の本数が等しい場合は大きい数だけ考えれば良い
A.sort(reverse=True)
s = set()
candidates = [] # [a, nums[a]]
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])


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

ans = ''
idx = N
digit = dp[N]
while digit:
  for a, n in candidates:
    if dp[idx-n] == dp[idx]-1:
      ans += str(a)
      digit -= 1
      idx -= n
      break

print(int(ans))

Submission status: Runtime Error

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

# 使うマッチ棒の本数が等しい場合は大きい数だけ考えれば良い
A.sort(reverse=True)
s = set()
candidates = [] # [a, nums[a]]
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])


dp1 = [0] * (N+1)
dp2 = [-1] * (N+1)
d = {}
for a, n in candidates:
  dp1[n] = 1
  dp2[n] = 0
  d[n] = a

for i in range(N+1):
  for a, n in candidates:
    if i >= n and dp1[i-n]:
      if dp1[i] < dp1[i-n] + 1:
        dp1[i] = dp1[i-n] + 1
        dp2[i] = i-n

ans = []
idx = N
while idx:
  next_idx = dp2[idx]
  ans.append(d[idx - next_idx])
  idx = next_idx

ans.sort(reverse=True)
print(''.join(list(map(str, ans))))

Submission status: Runtime Error

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

# 使うマッチ棒の本数が等しい場合は大きい数だけ考えれば良い
A.sort(reverse=True)
s = set()
candidates = [] # [a, nums[a]]
for a in A:
  if nums[a] in s:
    continue
  s.add(nums[a])
  candidates.append([a, nums[a]])

# dp[i] : ちょうどi本のマッチ棒で作ることができる最大の整数
dp = [0] * (N+1)
for a, n in candidates:
  dp[n] = a

for i in range(N+1):
  for a, n in candidates:
    if i >= n and dp[i-n]:
      temp = list(str(dp[i-n])) + [str(a)]
      temp.sort(reverse=True)
      temp = int(''.join(temp))
      dp[i] = max(dp[i], temp)

print(dp[-1])

Submission status: Runtime Error

Solution code:
d = {
    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(reverse=True)

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


for a in A:
    for j in range(d[a], N + 1):
        dp[j] = max(dp[j], dp[j - d[a]] + 1)

ans = ""
remain = dp[N]
match = N
while match > 0:
    for a in A:
        if dp[match - d[a]] == remain - 1:
            ans += str(a)
            match -= d[a]
            remain -= 1
            break

print(ans)

Submission status: Runtime Error

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A = A[::-1]
# print("#", A)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

Submission status: Runtime Error

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A = A[::-1]
# print("#", A)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(100000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if j < j_str: continue
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

Submission status: Runtime Error

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A = A[::-1]
# print("#", A)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(10000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
j_str = 0
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if j < j_str: continue
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            j_str = j
            break

print(ans)

Submission status: Runtime Error

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

tab = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A_cmp = {}
for Ai in sorted(A):
    A_cmp[tab[Ai]] = Ai
A = list(A_cmp.values())
A.sort(key=lambda x: -x)

memo = [None] * (N + 1)
memo[0] = 0

import sys
sys.setrecursionlimit(10000)

def dp(X):
    if memo[X] != None: return memo[X]
    if X < 0: return -(1000000007)
    #
    rets = []
    for i, Ai in enumerate(A):
        rets.append(dp(X - tab[Ai]) + 1)
    #
    ret = max(rets)
    memo[X] = ret
    return ret

ans_len = dp(N)

N_tmp = N
ans = ''
for i in range(ans_len):
    for j, Aj in enumerate(A):
        if dp(N_tmp) - 1 == dp(N_tmp - tab[Aj]):
            ans += str(Aj)
            N_tmp -= tab[Aj]
            break

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(set(map(lambda x : int(x)//2, input().split())))
def gcd(x, y):
  return x if y == 0 else gcd(y, x % y)
def lcm(x, y):
  return (x * y) // gcd(x, y)
l = A[0]
for a in A[1:]:
  l = lcm(l, a)
ans = (M // l + 1) // 2
for a in A[1:]:
  if (l // a) % 2 == 0:
    ans = 0
    break
print(ans)

Submission status: Runtime Error

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

tab = [(1, 2),
       (2, 5),
       (3, 5),
       (4, 4),
       (5, 5),
       (6, 6),
       (7, 3),
       (8, 7),
       (9, 6)]
# tab.sort(key=lambda x: (x[1], -x[0]))

memo = [None] * (N + 1)

def dp(X):
    # print("#", X)
    if X == 0: return ''
    if X < 0: return 'a'
    if memo[X] != None: return memo[X]
    len_max = 0
    rets = []
    for Ai in A:
        if X - tab[Ai - 1][1] < 0: continue
        ret_tmp = str(Ai) + dp(X - tab[Ai - 1][1])
        if 'a' in ret_tmp: continue
        ret_tmp = ''.join(sorted(list(ret_tmp), key=lambda x: -int(x)))
        rets.append(ret_tmp)
        len_max = max(len_max, len(ret_tmp))
    for i in range(len(rets)):
        rets[i] = '0' * (len_max - len(rets[i])) + rets[i]
    #
    rets.sort()
    # print("#", rets)
    if len(rets) == 0:
        ret = 'a'
    else:
        ret = rets[-1].replace('0', '')
    #
    memo[X] = ret
    return ret

print(dp(N))

Submission status: Runtime Error

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

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

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

C=[]

for i in range(M):
    C.append((A[i],B[A[i]-1]))

INF = float('inf')

DP = [[-INF]*(N+1) for i in range(M+1)]
DP[0][0] = 0


for i in range(M):
    for j in range(N+1):
        DP[i+1][j] = DP[i][j]
        if j>=C[i][1]:
            DP[i+1][j] = max(DP[i+1][j],DP[i+1][j-C[i][1]]+1)

C.sort(key = lambda x: x[0],reverse=True)

current = N
current_i = 0
current_m = 0
S = ""
#print(DP)
while True:
    #print(current_m)
    if DP[M][current] == DP[M][current-C[current_m][1]] + 1:
        S = S + str(C[current_m][0])
        current -= C[current_m][1]
        current_i+=1
        if current_i == DP[M][N]:
            break
    else:
        current_m += 1
    #print(S)

print(S)

Submission status: Runtime Error

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

memo = ["-1"] * 10100


def MAX(x, y):
    if y[0] != '#' and (x == "#" or len(x) < len(y) or (len(x) == len(y) and x < y)):
        return y
    else:
        return x


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return "#"

    if memo[i] != "-1":
        return memo[i]

    if i == 0:
        return ""

    ret = "#"
    for x in a:
        ret = MAX(ret, dp(i - f[x]) + str(x))
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Runtime Error

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

memo = [-1]*10100


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return - 10 ** 100000
    if not (0 <= i and i < 10100):
        print(-1)
        exit()
    if memo[i] != -1:
        return memo[i]
    if i == 0:
        return 0
    ret = -10**100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Runtime Error

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

memo = [-1]*10100


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return - 10 ** 100000
    if not (0 <= i and i < 10100):
        raise RuntimeError
    if memo[i] != -1:
        return memo[i]
    if i == 0:
        return 0
    ret = -10**100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Runtime Error

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

memo = [-1]*100100

def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return - 10 ** 100000
    if memo[i] != -1:
        return memo[i]
    if i == 0:
        return 0
    ret = -10**100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Runtime Error

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

memo = [-1]*10010


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return - 10 ** 100000
    if memo[i] != -1:
        return memo[i]
    if i == 0:
        return 0
    ret = -10*100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Runtime Error

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

memo = [-1]*10010


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if memo[i] != -1:
        return memo[i]
    if i < 0:
        return -10**100000
    if i == 0:
        return 0
    ret = -10*100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))

Submission status: Runtime Error

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


dp=[0]*(N+1)
for j in range(M):
    need=B[A[j]-1]
    dp[need]=max(dp[need],A[j])

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

Submission status: Runtime Error

Solution code:
from itertools import product
e = [10,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = sorted(map(int, input().split()))
d = {}
for i in a:
    if e[i] not in d:
        d[e[i]] = i
    elif d[e[i]] < i:
        d[e[i]] = i

dd = sorted([[i[0] + j[0],i[1] * 10 + j[1]] for i,j in product(d.items(), d.items())] + [[k,v] for k,v in d.items()])
d = {}
for k,v in dd:
     if k not in d:
         d[k] = v
     elif d[k] < v:
        d[k] = v
dd = [[k,v] for k,v in sorted(d.items())]
# [print(k,v) for k,v in dd]
# print()
if 2 in d:
    kk = 2
    vv = 1
elif 3 in d:
    kk = 3
    vv = 7
else:
    kk = 10000
    vv = 0
    for match_num,num in dd:
        if kk > match_num and vv < num:
            kk = match_num
            vv = num
        elif kk * 2 > match_num and vv * len(str(vv)) + vv < num:
            kk = match_num
            vv = num
k = kk * 3
ans = []
while n - kk >= k:
    ans.append(vv)
    n -= kk

vv = 0
u = 0
# print(ans, n)
for i,j,k in product(dd,dd,dd):
    k_len = len(str(k[1]))
    j_len = len(str(j[1]))
    #if i[0] + j[0] + k[0] == n:
    #    print(i,j,k, i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1])
    if i[0] + j[0] + k[0] == n and i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1] > vv:
        vv = i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1]
        uu = i[1] * 10**(j_len) + j[1]
        u = k[1]
    if i[0] + j[0] == n and i[1] * 10**(j_len) + j[1] > vv:
        vv = i[1] * 10**(j_len) + j[1]
        uu = i[1]
        u = j[1]
tmp = ''.join(map(str, ans)) if ans else ''
print(str(uu) + tmp + str(u))
# print(vv,uu,u)

Submission status: Runtime Error

Solution code:
from itertools import product
e = [10,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = sorted(map(int, input().split()))
d = {}
for i in a:
    if e[i] not in d:
        d[e[i]] = i
    elif d[e[i]] < i:
        d[e[i]] = i

dd = sorted([[i[0] + j[0],i[1] * 10 + j[1]] for i,j in product(d.items(), d.items())] + [[k,v] for k,v in d.items()])
d = {}
for k,v in dd:
     if k not in d:
         d[k] = v
     elif d[k] < v:
        d[k] = v
dd = [[k,v] for k,v in sorted(d.items())]
# [print(k,v) for k,v in dd]
# print()
if 2 in d:
    kk = 2
    vv = 1
elif 3 in d:
    kk = 3
    vv = 7
else:
    kk = 10000
    vv = 0
    for match_num,num in dd:
        if kk > match_num and vv < num:
            kk = match_num
            vv = num
        elif kk * 2 > match_num and vv * len(str(vv)) + vv < num:
            kk = match_num
            vv = num
k = kk * 3
ans = []
while n - kk >= k:
    ans.append(vv)
    n -= kk

vv = 0
u = 0
# print(ans, n)
for i,j,k in product(dd,dd,dd):
    k_len = len(str(k[1]))
    j_len = len(str(j[1]))
    #if i[0] + j[0] + k[0] == n:
    #    print(i,j,k, i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1])
    if i[0] + j[0] + k[0] == n and i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1] > vv:
        vv = i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1]
        uu = i[1] * 10**(j_len) + j[1]
        u = k[1]
tmp = ''.join(map(str, ans)) if ans else ''
print(str(uu) + tmp + str(u))
# print(vv,uu,u)

Submission status: Runtime Error

Solution code:
from itertools import product
e = [10,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = sorted(map(int, input().split()))
d = {}
for i in a:
    if e[i] not in d:
        d[e[i]] = i

dd = sorted([[i[0] + j[0],i[1] * 10 + j[1]] for i,j in product(d.items(), d.items())] + [[k,v] for k,v in d.items()])
d = {}
for k,v in dd:
     if k not in d:
         d[k] = v
dd = [[k,v] for k,v in sorted(d.items())]
# [print(k,v) for k,v in dd]
# print()
if 2 in d:
    kk = 2
    vv = 1
    k = 6
elif 3 in d:
    kk = 3
    vv = 7
    k = 9
else:
    kk = 10000
    vv = 0
    for match_num,num in dd:
        if kk > match_num and vv < num:
            kk = match_num
            vv = num
        elif kk * 2 > match_num and vv * len(str(vv)) + vv < num:
            kk = match_num
            vv = num
    k = kk * 3
ans = []
while n - kk >= k:
    ans.append(vv)
    n -= kk

vv = 0
u = 0
# print(ans, n)
for i,j,k in product(dd,dd,dd):
    k_len = len(str(k[1]))
    j_len = len(str(j[1]))
    #if i[0] + j[0] + k[0] == n:
    #    print(i,j,k, i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1])
    if i[0] + j[0] + k[0] == n and i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1] > vv:
        vv = i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1]
        uu = i[1] * 10**(j_len) + j[1]
        u = k[1]
tmp = ''.join(map(str, ans)) if ans else ''
print(str(uu) + tmp + str(u))
# print(vv,uu,u)

Submission status: Runtime Error

Solution code:
from itertools import product
e = [10,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = sorted(map(int, input().split()))
d = {}
for i in a:
    if e[i] not in d:
        d[e[i]] = i

dd = sorted([[i[0] + j[0],i[1] * 10 + j[1]] for i,j in product(d.items(), d.items())] + [[k,v] for k,v in d.items()])
d = {}
for k,v in dd:
     if k not in d:
         d[k] = v
dd = [[k,v] for k,v in sorted(d.items())]
# [print(k,v) for k,v in dd]
# print()
if 2 in d:
    kk = 2
    vv = 1
    k = 6
elif 3 in d:
    kk = 3
    vv = 7
    k = 9
else:
    kk = 10000
    vv = 0
    for match_num,num in dd:
        if kk > match_num and vv < num:
            kk = match_num
            vv = num
        elif kk * 2 > match_num and vv * len(str(vv)) + vv < num:
            kk = match_num
            vv = num
    k = max([i[0] for i in dd])
ans = []
while n - kk >= k:
    ans.append(vv)
    n -= kk

vv = 0
u = 0
# print(ans, n)
for i,j,k in product(dd,dd,dd):
    k_len = len(str(k[1]))
    j_len = len(str(j[1]))
    #if i[0] + j[0] + k[0] == n:
    #    print(i,j,k, i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1])
    if i[0] + j[0] + k[0] == n and i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1] > vv:
        vv = i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1]
        uu = i[1] * 10**(j_len) + j[1]
        u = k[1]

print(str(uu) + ''.join(map(str, ans)) + str(u))
# print(vv,uu,u)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    A = LI()
    num2match = {
        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 a in A:
        match_need = num2match[a]
        dp[match_need] = max(str(dp[match_need]), str(a))
    for i in range(N+1):
        for a in A:
            match_need = num2match[a]
            if i - match_need > 0:
                if dp[i-match_need] == '':
                    continue
                old = dp[i]
                new = str(a) + dp[i-match_need]
                if len(old) > len(new):
                    dp[i] = old
                elif len(new) > len(old):
                    dp[i] = new
                else:
                    dp[i] = max(old, new)
    print(dp[N])
main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
AtoH = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
H = [AtoH[a] for a in A]
#print("H:", H)
 
dp = [0] * (N + 1)
dpl = [0] * (N + 1)

for i in range(M):
  h, a = H[i], A[i]
  dp[N-h] = max(dp[N-h], dp[N]+a)
  dpl[N-h] = 1

for dpi in range(N-1, -1, -1):
  if dp[dpi]:
    for m in range(M):
      h, a = H[m], A[m]
      if dpi-h>=0:
        if dp[dpi-h] < dp[dpi] + 10**dpl[dpi]*a:
          dp[dpi-h] = dp[dpi] + 10**dpl[dpi]*a
          dpl[dpi-h] = dpl[dpi] + 1
print(dp[0])

Submission status: Runtime Error

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

AtoH = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
H = [AtoH[a] for a in A]
#print("H:", H)

dp = [0] * (N + 1)
for i in range(M):
  h, a = H[i], A[i]
  dp[N-h] = max(dp[N-h], dp[N]+a)

for dpi in range(N-1, -1, -1):
  if dp[dpi]:
    for m in range(M):
      h, a = H[m], A[m]
      if dpi-h>=0:
        dp[dpi-h] = max(dp[dpi-h], dp[dpi] + 10**len(str(dp[dpi]))*a)

print(dp[0])