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:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.reverse()
match = [2,5,5,4,5,6,3,7,6]
dp = [0]*(N+1)
for i in range(N+1):
  kouho = 0
  for j in range(M):
    if i-match[A[j]-1] >= 0:
      if kouho < dp[i-match[A[j]-1]]+1:
        kouho = dp[i-match[A[j]-1]]+1
  dp[i] = kouho
ans = ''
while N > 0:
  for i in range(M):
    if dp[N-match[A[i]-1]] == dp[N]-1:
      if dp[N]-1 != 0:
        ans += str(A[i])
        N -= match[A[i]-1]
        break
      else:
        for k in range(M):
          if match[A[k]-1] == N:
            ans += str(A[k])
            N = 0
            break
print(ans)

Submission status: Runtime Error

Solution code:
#encoding: utf-8

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

A.sort()
A.reverse()

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

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

print(dp[N])

Submission status: Runtime Error

Solution code:
hn_kz = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
kz_hn = {}
n, m, *kzs = map(int, open(0).read().split())
# 本数から数を求める辞書を作る。同じ本数の数は大きい方を取る
for kz in kzs:
    ah = hn_kz[kz]
    if ah in kz_hn:
        kz_hn[ah] = max(kz_hn[ah], kz)
    else:
        kz_hn[ah] = kz
# 最小の本数をhmnに格納
hmn = min(kz_hn.keys())
# まず、最小の本数の数だけで桁[本数]の辞書を作る
kt_hn = {kt * hmn: kt for kt in range(n // hmn + 1)}
# 最小本数以外の数の辞書nkz_hnを作る
nkz_hn = kz_hn.copy()
del nkz_hn[hmn]

inf = 10 ** 9


def keta(hn):
    #    print(hn,kt_hn)
    if hn in kt_hn:
        return kt_hn[hn]
    elif hn < 0:
        return -inf
    else:
        maxketa = -inf
        for hni in nkz_hn.keys():
            newkt = keta(hn - hni) + 1
            if newkt > maxketa:
                maxketa = newkt
        kt_hn[hn] = maxketa
        return maxketa


ans = ""
nokori = n
while nokori > 0:
    for kh in sorted(kz_hn.items(), key=lambda xkh: xkh[1], reverse=True):
        if keta(nokori - kh[0]) == keta(nokori) - 1 and keta(nokori - kh[0]) >= 0:
            ans += str(kh[1])
            nokori -= kh[0]
            break

print(ans)

Submission status: Runtime Error

Solution code:
hn_kz = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
kz_hn = {}
n, m, *kzs = map(int, open(0).read().split())
# 本数から数を求める辞書を作る。同じ本数の数は大きい方を取る
for kz in kzs:
    ah = hn_kz[kz]
    if ah in kz_hn:
        kz_hn[ah] = max(kz_hn[ah], kz)
    else:
        kz_hn[ah] = kz
# 最小の本数をhmnに格納
hmn = min(kz_hn.keys())
# まず、最小の本数の数だけで桁[本数]の辞書を作る
kt_hn = {kt * hmn: kt for kt in range(n // hmn + 1)}
# 最小本数以外の数の辞書nkz_hnを作る
nkz_hn = kz_hn.copy()
del nkz_hn[hmn]

inf = 10**9

def keta(hn):
    #    print(hn,kt_hn)
    if hn in kt_hn:
        return kt_hn[hn]
    elif hn < 0:
        return -inf
    else:
        maxketa = -inf
        for hni in nkz_hn.keys():
            newkt = keta(hn - hni) + 1
            if newkt > maxketa:
                maxketa = newkt
        kt_hn[hn] = maxketa
        return maxketa

ans = ""
nokori = n
while nokori > 0:
    for kh in sorted(kz_hn.items(), key=lambda xkh: xkh[1], reverse=True):
        if keta(nokori - kh[0]) == keta(nokori) - 1 and keta(nokori)>0:
            ans += str(kh[1])
            nokori -= kh[0]
            break

print(ans)

Submission status: Runtime Error

Solution code:
hn_kz={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
kz_hn={}
n,m,*kzs=map(int,open(0).read().split())
#本数から数を求める辞書を作る。同じ本数の数は大きい方を取る
for kz in kzs:
    ah=hn_kz[kz]
    if ah in kz_hn:
        kz_hn[ah]=max(kz_hn[ah],kz)
    else:
        kz_hn[ah]=kz
kt_hn={0:0}
#本数から桁数を求める関数
inf=100
def keta(hn):
    if hn in kt_hn:
        return kt_hn[hn]
    elif hn<0:
        return -inf
    else:
        maxketa=-inf
        for hni in kz_hn.keys():
            newkt=keta(hn-hni)+1
            if newkt>maxketa:
                maxketa=newkt
        kt_hn[hn]=maxketa
        return maxketa
#目的の数を作る
ans=""
nokori=n
while nokori>0:
    for kh in sorted(kz_hn.items(),key=lambda xkh:xkh[1],reverse=True):
        if keta(nokori-kh[0])==keta(nokori)-1:
            ans+=str(kh[1])
            nokori-=kh[0]
            break
print(ans)

Submission status: Runtime Error

Solution code:
hn_kz={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
kz_hn={}
n,m,*kzs=map(int,open(0).read().split())
#本数から数を求める辞書を作る。同じ本数の数は大きい方を取る
for kz in kzs:
    ah=hn_kz[kz]
    if ah in kz_hn:
        kz_hn[ah]=max(kz_hn[ah],kz)
    else:
        kz_hn[ah]=kz
#最小の本数をhmnに格納
hmn=min(kz_hn.keys())
#まず、最小の本数の数だけで桁[本数]の辞書を作る
kt_hn={kt*hmn:kt for kt in range(n//hmn+1)}
#本数から桁数を求める関数
inf=100
def keta(hn):
    if hn in kt_hn:
        return kt_hn[hn]
    elif hn<0:
        return -inf
    else:
        maxketa=-inf
        for hni in kz_hn.keys():
            newkt=keta(hn-hni)+1
            if newkt>maxketa:
                maxketa=newkt
        kt_hn[hn]=maxketa
        return maxketa
#目的の数を作る
ans=""
nokori=n
while nokori>0:
    for kh in sorted(kz_hn.items(),key=lambda xkh:xkh[1],reverse=True):
        if keta(nokori-kh[0])==keta(nokori)-1:
            ans+=str(kh[1])
            nokori-=kh[0]
            break
print(ans)

Submission status: Runtime Error

Solution code:
hn_kz={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
kz_hn={}
n,m,*kzs=map(int,open(0).read().split())
#本数から数を求める辞書を作る。同じ本数の数は大きい方を取る
for kz in kzs:
    ah=hn_kz[kz]
    if ah in kz_hn:
        kz_hn[ah]=max(kz_hn[ah],kz)
    else:
        kz_hn[ah]=kz
#最小の本数をhmnに格納
hmn=min(kz_hn.keys())
#まず、最小の本数の数だけで桁[本数]の辞書を作る
kt_hn={kt*hmn:kt for kt in range(n//hmn+1)}
#最小本数以外の数の辞書nkz_hnを作る
nkz_hn=kz_hn.copy()
del nkz_hn[hmn]
#本数から桁数を求める関数
inf=100
def keta(hn):
    if hn in kt_hn:
        return kt_hn[hn]
    elif hn<0:
        return -inf
    else:
        maxketa=-inf
        for hni in nkz_hn.keys():
            newkt=keta(hn-hni)+1
            if newkt>maxketa:
                maxketa=newkt
        kt_hn[hn]=maxketa
        return maxketa
#目的の数を作る
ans=""
nokori=n
while nokori>0:
    for kh in sorted(kz_hn.items(),key=lambda xkh:xkh[1],reverse=True):
        if keta(nokori-kh[0])==keta(nokori)-1:
            ans+=str(kh[1])
            nokori-=kh[0]
            break
print(ans)

Submission status: Runtime Error

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

dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
cost = []
b = {}
for x in a:
    cost.append(dic[x])
    b[dic[x]] = x

cost = sorted(list(set(cost)))

dp = [0]*(n+1)
for x in cost:
    dp[x] = [b[x]]


for i in range(cost[0], n+1):
    for x in cost:
        if i - x > 0 and dp[i-x] != 0:
            dp[i] = dp[i-x] + [b[x]]
            break

print("".join(list(map(str,sorted(dp[-1], reverse=True)))))

Submission status: Runtime Error

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

dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
cost = []
b = {}
for x in a:
    cost.append(dic[x])
    b[dic[x]] = x

cost = sorted(list(set(cost)))

dp = [0]*(n+1)
for x in cost:
    dp[x] = [b[x]]


for i in range(cost[0]*2, n+1):
    for x in cost:
        if i - x > 0 and dp[i-x] != 0:
            dp[i] = dp[i-x] + [b[x]]
            break

print("".join(list(map(str,sorted(dp[-1], reverse=True)))))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+1)
ans=[0]*(n+1)
num=[0,2,5,5,4,5,6,3,7,6]
INF=10**18
for i in range(1,n+1):
  stack=[]
  for j in m:
    if i-num[j]>=0:
      stack.append(dp[i-num[j]])
    else:
      stack.append(-INF)
  dp[i]=max(stack)+1
  if dp[i]>0:
    ans[i] += ans[i-num[stack.index(max(stack))]]+num[stack.index(max(stack))]*10**(dp[i]-1)
print(ans[n])

Submission status: Runtime Error

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

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


def solve(N, num=0):
    if N < 0:
        return -1
    if N == 0:
        return num
    ans = 0
    for a in A:
        tmp_num = num
        if tmp_num == 0:
            tmp_num += a
        else:
            tmp_num += a*(10**len(str(tmp_num)))
        ans = max(solve(N-cost[a-1],tmp_num),ans)
    return ans

print(solve(N))

Submission status: Runtime Error

Solution code:
import math

matchNums=int(input().split(" ")[0])

DATA=list(map(int, input().split(" ")))
DATA=sorted(DATA)

num=[1,2,3,4,5,6,7,8,9]
born=[2,5,5,4,5,6,3,7,6]
numDict=dict(zip(num,born))

loop_max=[1,1,1,1,1,1,1,1,1]

for i in DATA:
    loop_max[i-1] = int(matchNums/numDict[i])

def calc(loop_max, matchNums):
    outputs=[]
    for one in range(loop_max[0]):
        for two in range(loop_max[1]):
            for three in range(loop_max[2]):
                for four in range(loop_max[3]):
                    for five in range(loop_max[4]):
                        for six in range(loop_max[5]):
                            for seven in range(loop_max[6]):
                                for eight in range(loop_max[7]):
                                    for nine in range(loop_max[8]):
                                        alls=one*2+two*5+three*5+four*4+five*5+six*6+seven*3+eight*7+nine*6
                                        if alls==matchNums:
                                            output=""
                                            output+="9"*nine
                                            output+="8"*eight
                                            output+="7"*seven
                                            output+="6"*six
                                            output+="5"*five
                                            output+="4"*four
                                            output+="3"*three
                                            output+="2"*two
                                            output+="1"*one
                                            outputs.append(output)
    return outputs

output=calc(loop_max, matchNums)
temp_max=[len(i) for i in output]
max_len = max(temp_max)
ref_output=[]
for i in output:
  if len(i)==max_len:
    
    ref_output.append(i)


output = sorted(ref_output,reverse=True)
print(output[-1])

Submission status: Runtime Error

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

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

dp = [-1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans = 0
n = N
while n > 0:
    for num in useful_num_list:
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans += num * (10**(dp[n]-1))
            n -= need_matches[num]
            break
print(ans)

Submission status: Runtime Error

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

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

dp = [-1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans =""
n = N
while n > 0:
    ans_scale = ""
    for num in useful_num_list:
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans_scale = str(num)
            n -= need_matches[num]
            break
    ans += ans_scale
print(ans)

Submission status: Runtime Error

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

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

max_num_dict = {}
for a in A:
    if need_matches[a] in max_num_dict:
        if a > max_num_dict[need_matches[a]]:
            max_num_dict[need_matches[a]] = a
    else:
        max_num_dict[need_matches[a]] = a

useful_num_list = list(max_num_dict.values())
dp = [-1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans =""
n = N
while n > 0:
    ans_scale = ""
    for num in useful_num_list:
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans_scale = str(num)
            n -= need_matches[num]
            break
    ans += ans_scale
print(ans)

Submission status: Runtime Error

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

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

max_num_dict = {}
for a in A:
    if need_matches[a] in max_num_dict:
        if a > max_num_dict[need_matches[a]]:
            max_num_dict[need_matches[a]] = a
    else:
        max_num_dict[need_matches[a]] = a

useful_num_list = list(max_num_dict.values())
dp = [0] * (N+1)
for i in range(1, N+1):
    max_scale = -1
    for num in useful_num_list:
        if need_matches[num] <= i:
            scale = dp[i-need_matches[num]] + 1
            if max_scale < scale:
                max_scale = scale
    dp[i] = max_scale

useful_num_list.sort(reverse=True)
ans =""
n = N
while n > 0:
    ans_scale = ""
    for num in useful_num_list:
        if dp[n] - 1 == dp[n - need_matches[num]]:
            ans_scale = str(num)
            n -= need_matches[num]
            break
    ans += ans_scale
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[""]*(n+1)
a=sorted(list(map(int,input().split())))
e=[2,5,5,4,5,6,3,7,6]
d=[]
s=[]
for i in range(len(a)-1,-1,-1):
    if e[a[i]-1] not in s:
        s.append(e[int(a[i])-1])
        d.append(str(a[i]))
        p[e[a[i]-1]]=str(a[i])
for i in range(1,n+1):
    c=[]
    if len(p[i])!=0:
        c.append(int(p[i]))
    for j in range(len(s)):
        if i-s[j]>=0:
            if len(p[i-s[j]])!=0:
                c.append(max(int(p[i-s[j]]+d[j]),int(int(d[j]+p[i-s[j]]))))
    else:
        p[i]=("" if len(c)==0 else str(max(c)))
print(p[-1])

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
p=[""]*(n+1)
a=list(map(str,input().split()))
e=[2,5,5,4,5,6,3,7,6]
s=[]
for i in a:
    s.append(e[int(i)-1])
    p[e[int(i)-1]]=str(i)
for i in range(1,n+1):
    c=[]
    if len(p[i])!=0:
        c.append(int(p[i]))
    for j in range(m):
        if i-s[j]>=0:
            if len(p[i-s[j]])!=0:
                c.append(max(int(p[i-s[j]]+a[j]),int(int(a[j]+p[i-s[j]]))))
    else:
        p[i]=("" if len(c)==0 else str(max(c)))
print(p[-1])

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache


fin = sys.stdin.readline
num_matches_required = {n: nmatches for n, nmatches 
    in zip(range(1, 10), (2, 5, 5, 4, 5, 6, 3, 7, 6))}

N, M = map(int, fin().split())
nums = sorted(map(int, fin().split()), reverse=True)

@lru_cache(None)
def rec(i):
    if i < 0: 
        return float('-inf')
    elif i == 0: 
        return 0
    else:
        return max(
            rec(i - num_matches_required[num]) for num in nums
        ) + 1


num_digits = rec(N)
cur_num_matches = N
result = []
while cur_num_matches:
    for num in nums:
        if rec(cur_num_matches - num_matches_required[num]) == num_digits - len(result) - 1:
            result.append(str(num))
            cur_num_matches -= num_matches_required[num]
            break

print("".join(result))

Submission status: Runtime Error

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

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

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

A.sort(reverse=True)

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

print result

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(2*10**4)

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

INF = 10**15
# 各数字の消費マッチ棒
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)


# N=nのときの解に対応するベクトルを返す
@lru_cache(maxsize=None)
def dfs(n):
    return (
        [-INF for _ in range(9)] if n < 0 else
        [0 for _ in range(9)] if n == 0 else
        max(
            (
                [
                    t + 1 if i == a else t
                    for i, t in enumerate(dfs(n - C[a]), start=1)
                ]
                for a in A
            ),
            key=lambda x: [sum(x)] + list(reversed(x))
        )
    )


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

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

INF = 10**15
# 各数字の消費マッチ棒
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)


# N=nのときの解に対応するベクトルを返す
@lru_cache(maxsize=None)
def dfs(n):
    return (
        [-INF for _ in range(9)] if n < 0 else
        [0 for _ in range(9)] if n == 0 else
        max(
            (
                [
                    t + 1 if i == a else t
                    for i, t in enumerate(dfs(n - C[a]), start=1)
                ]
                for a in A
            ),
            key=lambda x: [sum(x)] + list(reversed(x))
        )
    )

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
Q = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

QA = [(Q[A[i]], A[i]) for i in range(M)]
QA.sort()

n2 = QA.count((5,2))
n3 = QA.count((5,3))
n5 = QA.count((5,5))
n6 = QA.count((6,6))
n9 = QA.count((6,9))

if n2 > 0 and n3 > 0:
    QA.remove((5,2))
if n3 > 0 and n5 > 0:
    QA.remove((5,3))
if n2> 0 and n5 > 0:
    QA.remove((5,2))
if n6 > 0 and n9 > 0:
    QA.remove((6,6))



def f(used_q, used_a):
    if used_q > N:
        return
    elif used_q == N:
        s = sorted(used_a, reverse=True)
        s = [str(i) for i in s]
        print("".join(s))
        sys.exit()

    for qa in QA:
        q, a = qa[0], qa[1]
        used_a.append(a)
        f(used_q + q, used_a)
        del used_a[-1]

l = []
f(0, l)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
Q = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

QA = [(Q[A[i]], A[i]) for i in range(M)]
QA.sort()

def f(used_q, num):
    if used_q > N:
        return -float("inf")
    elif used_q == N:
        s = sorted(list(str(num)),reverse=True)
        print("".join(s))
        sys.exit()
        return num

    ret = 0
    for qa in QA:
        q = qa[0]
        a = qa[1]
        ret = max(ret,f(used_q + q, num * 10 + a))
    return ret

f(0,0)

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

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

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

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

ans = ""
i = N
for _ in range(dp[-1]):
    for a in A:
        if dp[i]-1 == dp[i-nums[a]]:
            ans += str(a)
            i = i-nums[a]
            break
print(ans)

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

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

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

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

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

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

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

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

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

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

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

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

dp = [0]*(N+1)

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

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

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

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

dp = [0]*(N+1)

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

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

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)

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

dp = [0]*(N+1)

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

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

Submission status: Runtime Error

Solution code:

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

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

#同じ画数の数字を除く
tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key = lambda x:-x[1])

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

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

Submission status: Runtime Error

Solution code:
N,M = map(int,(input().split()))
A = list(map(int,input().split()))
cost = sorted(list(zip([[2,5,5,4,5,6,3,7,6][a-1] for a in A],A)),key = lambda x: (x[0],-x[1]))

#同じ画数の数字を除く
tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1
cost.sort(key = lambda x:-x[1])

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
nn=[[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[6,6],[8,7]]
n,m=map(int,input().split())
a=input().split()
for i in range(m):
  a[i]=int(a[i])
b=[]
for i in range(9):
  if nn[i][0] in a:
    b.append(nn[i])
  
c=[b[0]]
del b[0]
for i in range(len(b)):
  t=0
  for j in range(len(c)):
    if b[i][1] == c[j][1]:
      t=1
      break
  if t==1:
    continue
  c.append(b[i])
  
t=n//c[0][1]
n-=c[0][1]*t
a=c[0]
del c[0]
for i in range(len(c)):
  c[i][1]-=a[1]

ans=""
while c[0][1] <= n:
  for i in range(len(c)):
    i=len(c)-1-i
    if c[i][1]<=n:
      ans+=str(c[i][0])
      n-=c[i][1]
      t-=1
      break
      
ans+=str(a[0])*t
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
# マッチをi本使った時に出来る最大値を算出するDP
dp = [-9999999 for x in range(N + 1)]
dp[0] = 0
# iを作るために使うマッチ棒の本数
# 今回０は使わない為INF
NUM = [0,2,5,5,4,5,6,3,7,6]

for i in range(1, N + 1):
    for j in reversed(range(1, len(NUM))):
        if j not in A or i - NUM[j] < 0:
            continue
        dp[i] = max(dp[i - NUM[j]] + 1, dp[i])

# マッチを消費した場合の桁数が同じで、数字が大きい物を選ぶ
A.sort(reverse=True)
ans = 0
idx = len(dp) - 1
for i in range(max(dp)):
    for j in A:
        if dp[idx - NUM[j]] == dp[idx] - 1:
            ans = ans * 10 + j
            idx = idx - NUM[j]
            break

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
# マッチをi本使った時に出来る最大値を算出するDP
dp = [-9999999 for x in range(N + 1)]
dp[0] = 0
# iを作るために使うマッチ棒の本数
# 今回０は使わない為INF
NUM = [0,2,5,5,4,5,6,3,7,6]

for i in range(1, N + 1):
    for j in reversed(range(1, len(NUM))):
        if j not in A or i - NUM[j] < 0:
            continue
        dp[i] = max(dp[i - NUM[j]] + 1, dp[i])

# マッチを消費した場合の桁数が同じで、数字が大きい物を選ぶ
A.sort(reverse=True)
ans = 0
idx = len(dp) - 1
for i in range(max(dp)):
    for j in A:
        if dp[idx - NUM[j]] == dp[idx] - 1:
            ans = ans * 10 + j
            idx = idx - NUM[j]
            break

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

key = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
#k = [1, 7, 4, 5, 3, 2, 9, 6, 8]

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

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

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

i = dp(1)
a.sort()

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

print(int(s))