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:
from functools import lru_cache
def sub():
    N, M = [int(e) for e in input().split()]
    As = [e for e in input().split()]

    d_cost = {
            "1": 2,
            "2": 5,
            "3": 5,
            "4": 4,
            "5": 5,
            "6": 6,
            "7": 3,
            "8": 7,
            "9": 6,
            }
    
    
    NINF = -10**12
    @lru_cache(maxsize=None)   
    def dp(a_life):
        if a_life == 0:
            return 0
        cc = [a_life - d_cost[a] for a in As]
        cc = [c for c in cc if c >= 0]
        if len(cc) == 0:
            return NINF
        buf = [dp(c) + 1 for c in cc]
        return max(buf)
    
    Lmax = dp(N)
    print(Lmax)
    
    life = N
    buf = []
    for i in range(Lmax):
        oks = [a for a in As if dp(life - d_cost[a]) == Lmax - (i+1)]
        a_selected = max(oks)
        buf.append(a_selected)
        life = life - d_cost[a_selected]
    print("".join(buf))


sub()

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

n, m = li()
a = list(li())

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = num + dp[i]

        elif i + cost <= n:
            dp[i+cost] = str(max(int(dp[i+cost]), int(num + dp[i])))

print(dp[n]

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
cost = [0,2,5,5,4,5,6,3,7,6] # cost[a[i]] = a[i]のコスト
dp = [-1]*(n+1)
dp[0] = 0

for i in range(2,n+1):
    for j in range(0,m):
        if dp[i-cost[a[j]]] == -1:
            continue
        else:
            dp[i] = max(dp[i],dp[i-cost[a[j]]]+1)

ans = list()
read = n
a.sort()
a.reverse()

while read > 0:
    for i in range(0,m):
        if read -cost[a[i]] < 0:
            continue
        if dp[read-cost[a[i]]] == dp[read]-1:
            ans.append(str(a[i]))
            read -= cost[a[i]]
            break
    
print("".join(ans))

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
a = list(map(int,input().split()))
cost = [0,2,5,5,4,5,6,3,7,6] # cost[a[i]] = a[i]のコスト
dp = [-1]*(n+1)
dp[0] = 0

for i in range(2,n+1):
    for j in range(0,m):
        if dp[i-cost[a[j]]] == -1:
            continue
        else:
            dp[i] = max(dp[i],dp[i-cost[a[j]]]+1)

ans = list()
read = n
for i in reversed(range(0,n-1)):
    if dp[i]+1 == dp[read]:
        if read-i in [2,3,4,7]:
            ans.append(str(cost.index(read-i)))
        elif read-i == 6:
            if 9 in a:
                ans.append(str(9))
            else:
                ans.append(str(6))
        elif read -i == 5:
            if 5 in a:
                ans.append(str(5))
            elif 3 in a:
                ans.append(str(3))
            else:
                ans.append(str(2))
        read = i
ans.sort()
print("".join(reversed(ans)))

Submission status: Runtime Error

Solution code:
match_dict = {}
match_dict[1] = 2
match_dict[2] = 5
match_dict[3] = 5
match_dict[4] = 4
match_dict[5] = 5
match_dict[6] = 6
match_dict[7] = 3
match_dict[8] = 7
match_dict[9] = 6
INF = 10 ** 9
memo = {}

N,M = map(int, input().split())
line_list = list(map(int, input().split()))
line_list.sort()
line_list.reverse()
#print(line_list)

def dp(i):
    if i < 0:
        return -1 * INF
    if i == 0:
        return 0
    
    if i in memo:
        return memo[i]

    cur_max_digit = -1 * INF
    for num in line_list:
        cur_max_digit = max(dp(i - match_dict[num]), cur_max_digit)
    memo[i] = cur_max_digit + 1
    return cur_max_digit + 1

digit = dp(N) 
#print(digit)
ret = 0
for i in range(digit):
    for num in line_list:
        if digit - (i + 1) == dp(N - match_dict[num]):
            ret += num * 10**(digit - (i + 1))
            N -= match_dict[num]
            break
print(ret)

Submission status: Runtime Error

Solution code:
match_dict = {}
match_dict[1] = 2
match_dict[2] = 5
match_dict[3] = 5
match_dict[4] = 4
match_dict[5] = 5
match_dict[6] = 6
match_dict[7] = 3
match_dict[8] = 7
match_dict[9] = 6
INF = 10 ** 9
memo = {}

N,M = map(int, input().split())
line_list = list(map(int, input().split()))
line_list.sort()
line_list.reverse()
#print(line_list)

def dp(i):
    if i < 0:
        return -1 * INF
    if i == 0:
        return 0
    
    if i in memo:
        return memo[i]

    cur_max_digit = -1 * INF
    for num in line_list:
        cur_max_digit = max(dp(i - match_dict[num]), cur_max_digit)
    memo[i] = cur_max_digit + 1
    return cur_max_digit + 1

digit = dp(N) 
#print(digit)
ret = 0
for i in range(digit):
    for num in line_list:
        if digit - (i + 1) == dp(N - match_dict[num]):
            ret += num * 10**(digit - (i + 1))
            N -= match_dict[num]
print(ret)

Submission status: Runtime Error

Solution code:
import collections
N, M = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
n_m = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
m_n = {}
for a in A:
    m_n[n_m[a]] = a
countm = len(m_n)
dp = collections.defaultdict(lambda: -float('inf'))
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = max(dp[i - m] + 1 for m, n in m_n.items())
ans = ''
ms = sorted(m_n.keys(), key=lambda _: m_n[_], reverse=True)
d = dp[N]
while N:
    for m in ms:
        if dp[N - m] == dp[N] - 1:
            N -= m
            ans += f'{m_n[m]}'
            break
print(ans)

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
  l = [0,2,5,5,4,5,6,3,7,6]
  n,m = list(map(int,input().split()))
  a = list(map(int,input().split()))
  res = ''
  INF = 10**4
  
  dp = [[0,0] for i in range(n+1)]
  for i in range(n):
    for j in range(m):
      if dp[i][1] + l[a[j]] != i + l[a[j]] or i + l[a[j]] > n:
        pass
      else:
        dp[i + l[a[j]]][0] = max(dp[i][0] + 1, dp[i + l[a[j]]][0])
        dp[i + l[a[j]]][1] = dp[i][1] + l[a[j]]
  for i in range(1,n): 
    if dp[i][0] == 0:
      dp[i][0] = -INF
    else:
      pass
  
  a.sort(reverse = True)
  i = n
  while i > 0:
    for j in range(m):
      if dp[i - l[a[j]]][0] + 1 == dp[i][0]:
        res += str(a[j])
        i -= l[a[j]]
        break
      else:
        pass
  print(res)

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
  l = [0,2,5,5,4,5,6,3,7,6]
  n,m = list(map(int,input().split()))
  a = list(map(int,input().split()))
  res = ''
  INF = 10**4
  
  dp = [[0,0] for i in range(n+1)]
  for i in range(n):
    for j in range(m):
      if dp[i][1] + l[a[j]] != i + l[a[j]] or i + l[a[j]] > n:
        pass
      else:
        dp[i + l[a[j]]][0] = max(dp[i][0] + 1, dp[i + l[a[j]]][0])
        dp[i + l[a[j]]][1] = dp[i][1] + l[a[j]]
  for i in range(1,n): dp[i][0] = -INF if dp[i][0] == 0 else dp[i][0]
  
  a.sort(reverse = True)
  i = n
  for k in range(dp[n][0], 0, -1):
    for j in range(m):
      if dp[i - l[a[j]]][0] + 1 == dp[i][0]:
        res += str(a[j])
        i -= l[a[j]]
        break
      else:
        pass
  print(res)

Submission status: Runtime Error

Solution code:
N,M = [ int(it) for it in input().split() ]
li = [ int(it) for it in input().split() ]

comall = [-1,2,5,5,4,5,6,3,7,6]
com = [ (i,comall[i]) for i in li ]
com.sort( key=lambda x:-x[0])

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

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

match = N
keta = dp[N]
st = ""


for i in range( 10000 ):
  for j,c in com:
    if (keta-1==dp[match-c]):
      keta-=1
      match-=c
      st+=str(j)
      break
  if (match==0):
    break
print ( st )

Submission status: Runtime Error

Solution code:

n, _ = map(int,input().split())
a = list(map(int, input().split()))
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dp = [0] * (n + 1)


def calc(num, new):
    if num == 0:
        return 0
    num_str = str(num)
    new_str = str(new)
    sstr_list = list(str(num)) + list(str(new))
    sstr_list.sort(reverse=True)
    return int("".join(sstr_list))


s = set()
for x in range(2, 8):
    for i in a:
        if x > dic[i]:
            dp[x] = max(dp[x], calc(dp[x - dic[i]], i))
        elif x == dic[i]:
            dp[x] = max(dp[x], i)
    if dp[x]:
        for num in str(dp[x]):
            s.add(int(num))

for x in range(n + 1):
    for i in s:
        if x > dic[i]:
            dp[x] = max(dp[x], calc(dp[x - dic[i]], i))

print(dp[n])

Submission status: Runtime Error

Solution code:

n, _ = map(int,input().split())
a = list(map(int, input().split()))
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
dp = [0] * (n + 1)


def calc(num, new):
    if num == 0:
        return 0
    num_str = str(num)
    new_str = str(new)
    sstr_list = list(str(num)) + list(str(new))
    sstr_list.sort(reverse=True)
    return int("".join(sstr_list))


for i in a:
    dp[dic[i]] = max(dp[dic[i]], i)

for x in range(n + 1):
    for i in a:
        if x >= dic[i]:
            dp[x] = max(dp[x], calc(dp[x - dic[i]], i))

print(dp[n])

Submission status: Runtime Error

Solution code:
N, M = [int(a) for a in input().split(" ")]
ctab = {"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
A = [(a, ctab[a]) for a in input().split(" ")]
prev, curr = ([None]*(N+1), [None]*(N+1))
for char, cost in A:
    if not prev[cost] or char>prev[cost]:
        prev[cost] = char
ans = ""
while any(prev):
    for i in range(1, N+1):
        curr[i] = None
    for i in range(1, N+1):
        s = prev[i]
        if not s:
            continue
        for char, cost in A:
            if i+cost <= N:
                tmps = char+s
                if not curr[i+cost] or tmps > curr[i+cost]:
                    curr[i+cost] = tmps
    if curr[N] is not None:
        ans = curr[N]
    curr, prev = prev, curr
print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(a) for a in input().split(" ")]
ctab = {"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
A = [(a, ctab[a]) for a in input().split(" ")]
prev = [None]*(N+1)
curr = [None]*(N+1)
for char, cost in A:
    if not prev[cost] or char>prev[cost]:
        prev[cost] = char

ans = ""
while any(prev):
    for i in range(1, N+1):
        curr[i] = None
    for i in range(1, N+1):
        s = prev[i]
        if not s:
            continue
        for char, cost in A:
            tmps = char+s
            if i+cost <= N:
                if not curr[i+cost] or tmps > curr[i+cost]:
                    curr[i+cost] = tmps
    if curr[N] is not None:
        ans = curr[N]
    curr, prev = prev, curr
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import insort_left
N, M = [int(a) for a in input().split(" ")]
ctab = {"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
A = [(a, ctab[a]) for a in input().split(" ")]
prev = [None]*(N+1)
curr = [None]*(N+1)
for char, cost in A:
    if not prev[cost] or char>prev[cost]:
        prev[cost] = char

def insert(s, char):
    ls = list(s)[::-1]
    insort_left(ls, char)
    return int("".join(ls[::-1]))

tmp = ""
while any(prev):
    for i in range(1, N+1):
        maxval = -1
        for char, cost in A:
            if i-cost>=0 and prev[i-cost]:
                val = insert(prev[i-cost], char)
                maxval = val if val > maxval else maxval
        curr[i] = str(maxval) if maxval > 0 else None
    if curr[N] is not None:
        tmp = curr[N]
    curr, prev = prev, curr
print(tmp)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    cs = [0, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 ]
    dp = [-float('inf')] * (N + 1)

    dp[0] = 0
    for i in range(1, len(dp)):
        for a in A:
            if 0 <= i - cs[a]:
                dp[i] = max(dp[i], dp[i-cs[a]] + 1)
    i = N
    ret = 0
    while 0 < dp[i]:
        for a in A:
            c = cs[a]
            if dp[i] == (dp[i - c] + 1):
                i -= c
                ret = 10 * ret + a
                break
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    result = solve(N, M, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

f = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}
A = sorted(A, reverse=True)

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

ans = ''
num, digit = N, dp[N]
while num > 0:
    for a in A:
        if dp[num - f[a]] == digit - 1:
            ans += str(a)
            num -= f[a]
            digit -= 1
            break
print(ans)

Submission status: Runtime Error

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

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


dp = [-1*inf]*(N+1)
dp[0] = 0
for i in range(1,N+1):
  dp_new = 0
  for j in A:
    if i - number[j] >= 0:
      if dp[i-number[j]] +1 > dp_new:
        dp[i] = dp[i-number[j]] +1
        dp_new = dp[i]

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

print(int(ans))

Submission status: Runtime Error

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

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


dp = [-1*inf]*(N+1)
dp[0] = 0
for i in range(1,N+1):
  dp_new = 0
  for j in A:
    if i - number[j] >= 0:
      if dp[i-number[j]] +1 > dp_new:
        dp[i] = dp[i-number[j]] +1

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

print(int(ans))

Submission status: Runtime Error

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

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

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

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		dp_src=dp[i-match_cnt]  #dpの遷移元
		if 0<=i-match_cnt and dp_src is not None:
			if dp[i] is None:
				dp[i]=dp_src+str(a)
			else:
				if int(dp[i])<int( dp_src+str(a) ):
					dp[i]=dp_src+str(a)
				
print dp[N]

Submission status: Runtime Error

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

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

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

dp=[ None for i in range(N+1) ] 
dp[0]=""

for i in range(N+1):
	for a in A:
		match_cnt=match[a]
		if dp[i-match_cnt] is not None:
			if dp[i] is None:
				dp[i]=dp[i-match_cnt]+str(a)
			else:
				if int(dp[i])<int( dp[i-match_cnt]+str(a) ):
					dp[i]=dp[i-match_cnt]+str(a)
				
print dp[N]

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)


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

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

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None

    if target > 0:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None
    elif target == 0:
        return nums
    else:
        return None


# dpを計算
dp = defaultdict(lambda: -1e18)
dp[0] = 0
dp[1] = 0

for i in range(2, N+1):
    dp[i] = max([dp[i-num_dict[a]]+1 for a in A])


num_count = dp[N]
# あまりの本数
mod = N - min_matches*num_count

# あまりをどう分配するか(DFS)
share = dfs([], mod, num_count)
out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
out_list = [str(item) for item in out_list]
print(''.join(out_list))

Submission status: Runtime Error

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

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

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None
    if target == 0:
        return nums
    elif target < 0:
        return None
    else:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break

Submission status: Runtime Error

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

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

# Aの各要素の画数
count_list = [num_dict[a] for a in A]

# 最小の画数
min_matches = min(count_list)

# 画数の最小の値のうち最大の数値
min_num_list = []
[min_num_list.append(a) for a in A if num_dict[a] == min_matches]
min_num = max(min_num_list)


# 数値とあまり消化数のペア
A.sort(reverse=True)
res = {a: num_dict[a]-min_matches for a in A}


def dfs(nums, target, num_count):
    if len(nums) > num_count:
        return None
    if target == 0:
        return nums
    elif target < 0:
        return None
    else:
        for a in A:
            ret = dfs(nums+[a], target-res[a], num_count)
            if ret is not None:
                return ret
        return None


for num_count in range(N//min_matches, 0, -1):
    # あまりの本数
    mod = N - min_matches*num_count

    print(num_count, mod, num_count)

    # あまりをどう分配するか(DFS)
    share = dfs([], mod, num_count)
    if share is not None:
        out_list = sorted([min_num]*(num_count-len(share))+share, reverse=True)
        out_list = [str(item) for item in out_list]
        print(''.join(out_list))
        break

Submission status: Runtime Error

Solution code:
v=[-1,2,5,5,4,5,6,3,7,6]

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

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

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))

Submission status: Runtime Error

Solution code:
"""
1,2,3,4,5,6,7,8,9
2,5,5,4,5,6,3,7,6

"""

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

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

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

for a in reversed(A):
	dp[v[a]] = 1
	mp[v[a]] = [a]

for i in range(N+1):
	for a in A:
		if i-v[a] >= 0 and dp[i-v[a]] > 0 and dp[i] < 1 + dp[i-v[a]]:
			dp[i] = 1 + dp[i-v[a]]
			mp[i] = [a] + mp[i-v[a]]

print("".join(map(str, mp[N])))

Submission status: Runtime Error

Solution code:
"""
1,2,3,4,5,6,7,8,9
2,5,5,4,5,6,3,7,6

"""

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

N,M=map(int, input().split())
A=sorted(map(int, input().split()), reverse=True)
B=sorted(set([v[i] for i in A]))

dp=[0]*(N+1)

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

ans=[None]*dp[N]
for i in range(len(ans)):
	for a in A:
		if dp[N] == 1 + dp[N-v[a]]:
			if i+1 == len(ans) and N - v[a] > 0:
				continue
			N -= v[a]
			ans[i] = a
			break

print("".join(map(str, sorted(ans, reverse=True))))

Submission status: Runtime Error

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


def matchnum(n):
    table = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return table[n - 1]


# dp[n] : n本使った時の桁数
dp = [0] + [-INF for _ in range(N)]
for i in range(N + 1):
    for j, a_j in enumerate(A):
        if i - matchnum(a_j) >= 0:
            dp[i] = max(dp[i], dp[i - matchnum(a_j)] + 1)

l = dp[N]
m = N
ans = []
A = sorted(A, reverse=True)
while m > 0:
    for i, a_i in enumerate(A):
        if dp[m - matchnum(a_i)] == l - 1:
            ans.append(str(a_i))
            m -= matchnum(a_i)
            l -= 1
            break
print(''.join(ans))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
x=[0,2,5,5,4,5,6,3,7,6]
a=list(map(int,input().split()))
a.sort()
x=[ x[a[i]] for i in range(M) ]

p=[[-1 for j in range(M)] for i in range(N+10)]
p[0]=[0 for j in range(M)]

for i in range(N+1):
    for j in range(M):
        if p[i][0]>-1 and sum(p[i])+1>sum(p[i+x[j]]):
            p[i+x[j]]=[p[i][k] for k in range(M)]
            p[i+x[j]][j]+=1

        elif p[i][0]>-1 and sum(p[i])+1==sum(p[i+x[j]]):
            tmp=[p[i][k] for k in range(M)]
            tmp[j]+=1
            for k in range(M-1,-1,-1) and tmp!=p[i+x[j]]:
                if tmp[k] > p[i+x[j]][k] :
                    p[i+x[j]]=[tmp[k] for k in range(M)]
                    break


for i in range(M-1,-1,-1):
    for j in range(p[N][i]):
        print(a[i],end="")

Submission status: Runtime Error

Solution code:
from operator import itemgetter
#cost,value
matches = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
li = []
N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

def dfs(n,num,cand):
    if(n>=len(li) or num+li[n][1]>N):
        return False
    if(num+li[n][1]==N):
        if(li[n][0] in cand):
            cand[li[n][0]]+=1
        else:
            cand[li[n][0]]=1
        return True
    for i in range(n,len(li)):
        if(dfs(i,num+li[n][1],cand)):
            if(li[n][0] in cand):
                cand[li[n][0]]+=1
            else:
                cand[li[n][0]]=1
            return True
    return False


for x in A:
    li+=[(x,matches[x])]
li.sort(key=itemgetter(0))
li.reverse()
li.sort(key=itemgetter(1))
cand={}
dfs(0,0,cand)
ans = ''
for i in cand:
    ans = str(i)*cand[i]+ans

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
list=[]
L=[]
for key in range(9,0,-1):
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[1])
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num+1)] for j in range(N+1)]
dp[0]=[0]*(num+1)
#dp[i] N=iでの最大値
Non=[-1]*(num+1)
for i in range(N):
    ini=[]
    for j in range(num):
        if i+1-cost[j]>=0 and dp[i+1-cost[j]]!=Non:
            a=dp[i+1-cost[j]][:]
            a[j+1]+=1
            a[0]+=1
            ini.append(a)
    if ini:
        dp[i+1]=max(ini)
s=""
s1=""
Num=N
Keys=dic.keys()
Keys.reverse()
for i in range(dp[N][0]):
    for k in Keys:
        if Num-dic[k]>=0 and dp[Num][0]-1==dp[Num-dic[k]][0]:
            s1+=str(k)
            Num-=dic[k]
            break
print(s1)

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))


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

dig = [0] * (n+1)

inf = 10**9


for i in range(1, n + 1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if bef == 0:
                lst.append(dig[bef])
            else:
                if dig[bef] > 0:
                    lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""


def dp(i):
    k = -1
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[i] == 1:
            if bef == 0:
                maxi = max(maxi, num)
                k = 0
        else:
            if bef >= 0:
                if dig[bef] == dig[i] - 1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    if k >= 0:
        dp(k)


dp(n)
print(ans)

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

import sys
sys.setrecursionlimit(50000)

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1,n+1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i-mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""
def dp(i):
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[i] == 1:
            if bef == 0:
                maxi = max(maxi,num)
                k = 0
        else:
            if bef >= 0:
                if dig[bef] == dig[i]-1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    dp(k)

dp(n)
print(ans)

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

import sys
sys.setrecursionlimit(10000)

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1,n+1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i-mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""
def dp(i):
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[i] == 1:
            if bef == 0:
                maxi = max(maxi,num)
                k = 0
        else:
            if bef >= 0:
                if dig[bef] == dig[i]-1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    dp(k)

dp(n)
print(ans)

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1,n+1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i-mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1

ans = ""
def dp(i):
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if dig[i] == 1:
                if bef == 0:
                    maxi = max(maxi,num)
                    k = 0
            else:
                if dig[bef] == dig[i]-1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    dp(k)

dp(n)
print(ans)

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1,n+1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i-mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""
def dp(i):
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if dig[bef] == dig[i]-1 and (dig[bef] > 0 or bef == 0):
                if num > maxi:
                    maxi = num
                    k = bef
    dp(k)

dp(n)
print(ans)

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1,n+1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i-mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""
def dp(i):
    if i == 0:
        return
    global ans
    maxi = 0
    k = -1
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            if dig[bef] == dig[i]-1 and (dig[bef] > 0 or bef == 0):
                if num > maxi:
                    maxi = num
                    k = bef
    ans += str(maxi)
    if k >=0:
        dp(k)

dp(n)
print(ans)