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()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = sorted(list( set( C[a] for a in A)))
for i in range(2,N+1):
    for z in Z:
        if i >= z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
    print(dp)
s = N
ANS = [0]*10
while s != 0:
    _, b = dp[s]
    ANS[s-b] += 1
    if s == b:
        break
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans += str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split(' '))
ai = list(sorted(map(int, input().split(' '))))
required_maches = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

used_numbers = dict()

def evaluate(l):
    if l == None:
        return -9999999999999999999999999999999
    if l == []:
        return 0
    return int(''.join(reversed([str(i) for i in sorted(l)])))

min_maches = min([required_maches[x] for x in ai])
def find(matches_count_to_use):
    if matches_count_to_use not in used_numbers:
        if matches_count_to_use == 0:
            used_numbers[matches_count_to_use] = []
        elif matches_count_to_use < min_maches:
            used_numbers[matches_count_to_use] = None
        else:
            candidates = list(filter(
                lambda x: find(matches_count_to_use - required_maches[x]) != None, ai))
            if len(candidates) == 0:
                used_numbers[matches_count_to_use] = None
            else:
                number_to_use = max(candidates,
                    key=lambda x: evaluate(find(matches_count_to_use - required_maches[x]) + [x]))
                prev = find(matches_count_to_use - required_maches[number_to_use])
                used_numbers[matches_count_to_use] = prev + [number_to_use]
                
    return used_numbers[matches_count_to_use]
    
print(evaluate(find(n)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
*A, = map(int, input().split())
 
cost_define = [2,5,5,4,5,6,3,7,6]
 
C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])
 
#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)
 
#余ったら最大桁から増やしていく
res = ""
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (0 < c):
        if (c <= amari):
          n = min(keta, amari // c)
          amari -= (c * n)
          res += str(a) * n
          keta -= n
          found = True
          break
      elif (0 == c):
        found = False
        break
    if not found:
      res += str(min_cost_number) * keta
      keta = 0
      break
  else:
    res += str(min_cost_number) * keta
    keta = 0
    break
  #print(keta, res)
 
#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if (c <= amari):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  n = (amari // tmp_c)
  amari -= (tmp_c * n)
  #print(amari,tmp_c)

  new_res = res[:-(keta+n)] + str(tmp_a)*n
  if (0 < keta):
    new_res += res[-(keta):]
  res = new_res
  keta += n
 
print(res)

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_[1] < 1:
        return None
    elif N % min_[1] == 0:
        return [min_[0]] * (N // min_[1])
    else:
        for a, n in B:
            if (N // min_[1]) - ((N-n) // min_[1]) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret
        return None


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Submission status: Runtime Error

Solution code:
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    As = sorted(As, reverse=True)
    for i in range(N + 1):
        for a in As:
            c = Matches[a]
            if dp[i - c] == -1:
                continue
            if 0 <= i - c:
                dp[i] = max(dp[i],
                            dp[i - c] * 10 + a)
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=sorted([int(i) for i in input().split()],reverse=True)
num=[6,2,5,5,4,5,6,3,7,6]
INF=10**15
dp=[-INF for i in range(N+1)];dp[0]=0
for i in range(1,N+1):
    for j in range(M):
        dp[i]=max(dp[i],dp[i-num[A[j]]]+1)
K=N
i=0
ans=""
while(K>0):
    if dp[K-num[A[i]]]==dp[K]-1:
        ans=ans+str(A[i])
        K-=num[A[i]]
    else:
        i+=1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_[1] < 1:
        return None
    elif N % min_[1] == 0:
        return [min_[0]] * (N // min_[1])
    else:
        for a, n in B:
            if (N // min_[1]) - ((N-n) // min_[1]) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Submission status: Runtime Error

Solution code:
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}


def solve(N, M, As):
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    As = sorted(As, reverse=True)
    for i in range(N + 1):
        for a in As:
            c = Matches[a]
            if dp[i - c] == -1:
                continue
            if 0 <= i - c <= N:
                dp[i] = max(dp[i],
                                dp[i-c] * 10 + a)
    return dp[N]

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def main():
  remain, _ = list(map(int, input().split()))

  costs = list(map(int, input().split()))
  costs = [(c, COSTS[c]) for c in costs]
  costs.sort(key=lambda x:x[1])

  num, cost = costs[0]
  costs.sort(key=lambda x:-x[0])

  nums = [num] * (remain // cost)
  remain -= cost * len(nums)

  if remain != 0:
    new_costs = []
    exists = set([0])

    for n, c in costs:
      nc = c - cost

      if nc <= remain and nc not in exists:
        new_costs.append((n, nc))

    max_repeat = min(remain // min(v[1] for v in new_costs), len(nums))
    rep_nums_list = []

    for repeat in range(1, max_repeat + 1):
      for idxs in itertools.product(range(len(new_costs)), repeat=repeat):
        nc = sum(new_costs[i][1] for i in idxs)

        if nc != remain:
          continue

        rep_nums_list.append([new_costs[i][0] for i in idxs])

    #max_nums = [0] * len(nums)

    #for rep_nums in rep_nums_list:
    #  uns = [v for v in rep_nums if v > num]
    #  lns = [v for v in rep_nums if v < num]
    #  new_nums = nums[:]

    #  if len(uns) > 0:
    #    new_nums = uns + new_nums[len(uns):]

    #  if len(lns) > 0:
    #    new_nums = new_nums[:-len(lns)] + lns

    #  if new_nums > max_nums:
    #    max_nums = new_nums

    #nums = max_nums

  print(''.join(str(v) for v in nums), flush=True)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_[1] < 1:
        return None
    elif N % min_[1] == 0:
        return [min_[0]] * (N // min_[1])
    else:
        for a, n in B:
            if (N // min_[1]) - ((N-n) // min_[1]) == 1:
                ret = dp(N-n, B, min_[1])
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def main():
  remain, _ = list(map(int, input().split()))

  costs = list(map(int, input().split()))
  costs = [(c, COSTS[c]) for c in costs]
  costs.sort(key=lambda x:x[1])

  num, cost = costs[0]
  costs.sort(key=lambda x:-x[0])

  nums = [num] * (remain // cost)
  remain -= cost * len(nums)

  if remain != 0:
    new_costs = []
    exists = set([0])

    for n, c in costs:
      nc = c - cost

      if nc <= remain and nc not in exists:
        new_costs.append((n, nc))

    max_repeat = min(remain // min(v[1] for v in new_costs), len(nums))
    rep_nums_list = []

    for repeat in range(1, max_repeat + 1):
      for idxs in itertools.product(range(len(new_costs)), repeat=repeat):
        nc = sum(new_costs[i][1] for i in idxs)

        if nc != remain:
          continue

        rep_nums_list.append([new_costs[i][0] for i in idxs])

    max_nums = [0] * len(nums)

    for rep_nums in rep_nums_list:
      uns = [v for v in rep_nums if v > num]
      lns = [v for v in rep_nums if v < num]
      new_nums = nums[:]

      if len(uns) > 0:
        new_nums = uns + new_nums[len(uns):]

      if len(lns) > 0:
        new_nums = new_nums[:-len(lns)] + lns

      if new_nums > max_nums:
        max_nums = new_nums

    nums = max_nums

  print(''.join(str(v) for v in nums), flush=True)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split(' '))
ai = list(sorted(map(int, input().split(' '))))
required_maches = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

used_numbers = dict()

def evaluate(l):
    if l == None:
        return -9999999999999999999999999999999
    if l == []:
        return 0
    return int(''.join(reversed([str(i) for i in sorted(l)])))

min_maches = min([required_maches[x] for x in ai])
def find(matches_count_to_use):
    if matches_count_to_use not in used_numbers:
        if matches_count_to_use == 0:
            used_numbers[matches_count_to_use] = []
        elif matches_count_to_use < min_maches:
            used_numbers[matches_count_to_use] = None
        else:
            number_to_use = max(ai,
                key=lambda x: evaluate(find(matches_count_to_use - required_maches[x])))
            prev = find(matches_count_to_use - required_maches[number_to_use])
            if prev == None:
                used_numbers[matches_count_to_use] = None
            else:
                used_numbers[matches_count_to_use] = prev + [number_to_use]
    return used_numbers[matches_count_to_use]
    
print(evaluate(find(n)))

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = sorted(list( set( [ C[a] for a in A])))
for i in range(2,N+1):
    for z in Z:
        if i >= z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
b = 1
s = N
ANS = [0]*10
while b != 0:
    a, b = dp[s]
    ANS[s-b] += 1
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans += str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_ < 1:
        return None
    else:
        for a, n in B:
            if (N // min_) - ((N-n) // min_) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
*A, = map(int, input().split())
 
cost_define = [2,5,5,4,5,6,3,7,6]
 
C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])
 
#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)
 
#余ったら最大桁から増やしていく
res = ""
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (0 < c):
        if (c <= amari):
          n = max(keta, amari // c)
          amari -= (c * n)
          res += str(a) * n
          keta -= n
          found = True
          break
      elif (0 == c):
        found = False
        break
    if not found:
      res += str(min_cost_number) * keta
      keta = 0
      break
  else:
    res += str(min_cost_number) * keta
    keta = 0
    break
  #print(keta, res)
 
#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if (c <= amari):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  n = (amari // tmp_c)
  amari -= (tmp_c * n)
  #print(amari,tmp_c)
  #print(res, res[-(keta+1)], str(tmp_a))
  #res[-(keta+1)] = str(a)[0]
  new_res = res[:-(keta+n)] + str(tmp_a)*n
  if (0 < keta):
    new_res += res[-(keta):]
  res = new_res
  keta += n
 
print(res)

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split(' '))
ai = list(sorted(map(int, input().split(' '))))
required_maches = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

used_numbers = dict()

def evaluate(l):
    if l == None:
        return -999999999
    if l == []:
        return 0
    return int(''.join(reversed([str(i) for i in sorted(l)])))

min_maches = min([required_maches[x] for x in ai])
def find(matches_count_to_use):
    if matches_count_to_use not in used_numbers:
        if matches_count_to_use == 0:
            used_numbers[matches_count_to_use] = []
        elif matches_count_to_use < min_maches:
            used_numbers[matches_count_to_use] = None
        else:
            number_to_use = max(ai,
                key=lambda x: evaluate(find(matches_count_to_use - required_maches[x])))
            prev = find(matches_count_to_use - required_maches[number_to_use])
            if prev == None:
                used_numbers[matches_count_to_use] = None
            else:
                used_numbers[matches_count_to_use] = prev + [number_to_use]
    return used_numbers[matches_count_to_use]
    
print(evaluate(find(n)))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
num=[0,2,5,5,4,5,6,3,7,6]
canmake=dict()
b=[]
for i in a:
    b.append(num[i])
    if num[i] not in canmake.keys():
        canmake[num[i]]=i
b.sort()
c=[]
d=[]
amari=n%b[0]
longest=n//b[0]
if amari==0:print(str(b[0])*(n//b[0]))
#何ケタ減らすと丁度になるか求める
for i in range(1,len(b)):
    count=0
    now=amari
    while True:
        count+=1
        now+=b[0]
        if count>b[i]:break
        if now%b[i]==0:
            c.append(count-now//b[i])
            d.append((count,now//b[i],b[i]))
            break
res=min(c)
ans=[]
for i in range(c.count(res)):
    an=dict()
    idx=c.index(res)
    an[b[0]]=longest-d[idx][0]
    an[d[idx][2]]=d[idx][1]
    ans.append(an)
    c[idx]=-1

result=0
for i in ans:
    x=[]
    for i in an.keys():
        x.append((canmake[i],an[i]))
    x.sort(key=lambda y:y[0])
    re=''
    for i in range(len(x)):
        y=x.pop()
        re+=str(y[0])*y[1]
    ima=int(re)
    if ima>result:result=ima
        
if amari!=0:print(result)

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N // min_ == 1:
        for a, n in B:
            if n == N:
                return [a]
        return None
    else:
        for a, n in B:
            if (N // min_) - ((N-n) // min_) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
H = [0]*10
dp = [(0,0)]*(N+1)
for a in A:
    if H[C[a]] < a:
        H[C[a]] = a
H = [ str(h) for h in H]
for a in A:
    dp[C[a]] = (1,0)
Z = sorted(list( set( [ C[a] for a in A])))
for i in range(2,N+1):
    for z in Z:
        if i >= z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
b = 1
s = N
ANS = [0]*10
while b != 0:
    a, b = dp[s]
    ANS[s-b] += 1
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans += str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
H = [0]*10
dp = [(0,0)]*(N+1)
for a in A:
    if H[C[a]] < a:
        H[C[a]] = a
H = [ str(h) for h in H]
for a in A:
    dp[C[a]] = (1,0)
Z = sorted(list( set( [ C[a] for a in A])))
for i in range(2,N+1):
    for z in Z:
        if i >= z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
ans = ""
b = 1
s = N
while b != 0:
    a, b = dp[s]
    ans = H[s-b] + ans
    s = b
if int( ans[0]) < int( ans[-1]):
    ans = ans[::-1]
print( ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N // min_ == 1:
        for a, n in B:
            if n == N:
                return [a]
        return None
    else:
        for a, n in B:
            if (n - min_) <= (N % min_):
                ret = dp(N-n, B, min_)
                if ret is None:
                    continue
                else:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Submission status: Runtime Error

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

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

use_lis = [need_lis[i] for i in a]

use_lis.sort()

use_num_lis= []
for i in use_lis:
    if i ==2:
        use_num_lis.append(1)
    if i ==3:
        use_num_lis.append(7)
    if i==4:
        use_num_lis.append(4)
    if i==5:
        if 5 in a:
            use_num_lis.append(5)
        elif 3 in a:
            use_num_lis.append(3)
        else:
            use_num_lis.append(2)
    if i==6:
        if 9 in a:
            use_num_lis.append(9)
        else:
            use_num_lis.append(6)
    if i==7:
        use_num_lis.append(8)

ok_lis=[]
for i in range(use_lis[0]**(len(use_lis)-1)):
    ind_lis=[]
    for j in range(len(use_lis)-2,-1,-1):
        #print(j)
        ind_lis.append(i//(use_lis[0]**j))
        i -= (i//(use_lis[0]**j))*(use_lis[0]**j)
    #print(ind_lis)
        
    count = 0
    for i in range(len(use_lis)-1):
        count += use_lis[i+1]*ind_lis[i]
    #print(count)
    if (n - count) %use_lis[0]==0:
        #print(n-count)
        rest = n-count
        ok_lis.append([int(rest/use_lis[0])]+ind_lis)

res=[]
for i in ok_lis:
    res.append(sum(i))
max_lis = [i for i in range(len(res)) if res[i]==max(res)]

answers_lis=[]
for i in max_lis:
    answer=''
    use = ok_lis[i]
    num_lis=use_num_lis
    
    for k in range(len(use)):
        
        ind = np.argmax(np.array(num_lis))
        #print(ind)
        if use[ind]>0:
            count=0
            for j in range(use[ind]):
                #print(type(count))
                count+=(10**j)*num_lis[ind]
            count =str(count)
                #print(type(count))
            answer+=count
        num_lis[ind]=0
    answers_lis.append(answer)
        
    use_num_lis= []
    for i in use_lis:
        if i ==2:
            use_num_lis.append(1)
        if i ==3:
            use_num_lis.append(7)
        if i==4:
            use_num_lis.append(4)
        if i==5:
            if 5 in a:
                use_num_lis.append(5)
            elif 3 in a:
                use_num_lis.append(3)
            else:
                use_num_lis.append(2)
        if i==6:
            if 9 in a:
                use_num_lis.append(9)
            else:
                use_num_lis.append(6)
        if i==7:
            use_num_lis.append(8)
        
    
    

print(int(max(answers_lis)))

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N // min_ == 1:
        for a, n in B:
            if n == N:
                return [a]
    else:
        for a, n in B:
            if (n - min_) <= (N % min_):
                return [a] + dp(N-n, B, min_)


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
D = {}
if 1 in A:
    D[2] = '1'
if 7 in A:
    D[3] = '7'
if 4 in A:
    D[4] = '4'
if 2 in A:
    D[5] = '2'
if 3 in A:
    D[5] = '3'
if 5 in A:
    D[5] = '5'
if 6 in A:
    D[6] = '6'
if 9 in A:
    D[6] = '9'
if 8 in A:
    D[8] = '8'

def chmax(s, t):
    s, t = sorted(s, reverse=True), sorted(t, reverse=True)
    return ''.join(max(s, t))

dp = [['' for _ in range(N+1)] for _ in range(5001)]
if N < 100:
    start = 1
    for n, s in D.items():
        dp[1][n] = s
else:
    mini = min(D.keys())
    start = (N-100)//mini + 1
    dp[start][start*mini] = D[mini] * start

for i in range(start, 5001):
    for j in range(0, N+1):
        if dp[i][j] == '':
            continue
        for n, s in D.items():
            if j+n > N:
                continue
            dp[i+1][j+n] = chmax(dp[i+1][j+n], dp[i][j]+s)

for a in dp:
    if a[-1] != '':
        tmp = a[-1]
print(int(tmp))

Submission status: Runtime Error

Solution code:
#解説より
cost=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=sorted(map(int,input().split()))[::-1]
dp=[0]
for i in range(1,N+1):
    l=[dp[i-cost[a]]for a in A if i>=cost[a]]
    if len(l)==0:dp+=[-1]
    else:dp+=[max(l)+1]
S=''
Sum=0
for i in range(dp[N]):
    for a in A:
        if dp[N-Sum-cost[a]]==dp[N]-1-i:
            S+=str(a)
            Sum+=cost[a]
            break
print(S)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ucost = set([cost[a] for a in A])

DP = [-1]*(N+1)
DP[0] = 0
for a in A:
    DP[cost[a]] = 1

for i in range(N):
    if DP[i]:
        v = DP[i]
        for a in A:
            c = cost[a]
            if i + c > N:
                break
            DP[i+c] = max(DP[i+c], v+1)
rA = A[::-1]

t = N
ans = 0
while t:
    for a in rA:
        if DP[t] == DP[t - cost[a]] + 1:
            ans = 10*ans + a
            t -= cost[a]
            break
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ucost = set([cost[a] for a in A])

DP = [0]*(N+1)
for a in A:
    DP[cost[a]] = 1

for i in range(N):
    if DP[i]:
        v = DP[i]
        for c in ucost:
            if i + c > N:
                break
            DP[i+c] = max(DP[i+c], v+1)
rA = A[::-1]

t = N
ans = 0
while t:
    for a in rA:
        if DP[t] == DP[t - cost[a]] + 1:
            ans = 10*ans + a
            t -= cost[a]
            break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
def judge(N,n,list_new,A,min):
    # judge if we can make the perfect match
    if n == 1:
        if N in list_new:
            s = np.where(N==list_new)
            s = s[0].tolist()
            l = []
            for item in A[s]:
                l.append([item])
            return l
        else:
            return []
    listy = []
    list_here = np.sort(list_new)
    list_h = list_here[::-1]
    for i in range(len(list_h)):
        item = list_new[i]
        M = N-item
        m = n-1
        if M<min*m or item*m < M:
            pass
        else:
            s = judge(M,m,list_new,A,min)
            if s != []:
                for sin in s:
                    listy.append(np.append(sin,A[i]))
    if listy == []:
        return []
    else:
        return listy


list = [2,5,5,4,5,6,3,7,6]
s = input()
s = s.split()
N = int(s[0])
M = int(s[1])
t = input()
A = t.split()
list_new = []
for i in range(M):
    A[i] = int(A[i])
A = np.array(A)
for item in A:
    list_new.append(list[item-1])
list_new = np.array(list_new)
min = np.min(list_new)
q, mod = divmod(N,min)
a = np.where(list_new == min)
a = a[0].tolist()
num = A[a]
digit = max(num)
number = str(digit)*q

while True:
    a = judge(N,q,list_new,A,min)
    if a != []:
        listofnumbers = []
        for item in a:
            item.sort()
            string = ''
            for  i in item:
                string = str(i) + string
            listofnumbers.append(int(string))
        print(np.max(listofnumbers))
        break
    else:
        q = q-1

Submission status: Runtime Error

Solution code:
ort math

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-100000000000000000000
    tmp_keta=-1
    for j in A:
        tmp1=-100000000000000000000
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]!=0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            else:
                tmp1=j
                tmp1_keta=1
            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
    dp.append(tmp)
    keta.append(tmp_keta)
ans=dp[N]
print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = sorted(input().split(), reverse=True)

    dp = [-10007] * (n + 1)
    dp[0] = 0
    for i in a:
        step = mp[int(i)]
        for j in range(step, n + 1):
            dp[j] = max(dp[j - step] + 1, dp[j])

    i = n
    while i > 0:
        for x in a:
            step = mp[int(x)]
            if dp[i - step] == dp[i] - 1:
                sys.stdout.write(x)
                i -= step
                break
    print()

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
n=[0,2,5,5,4,5,6,3,7,6]
num=[0]*8
for a in A:
    num[n[a]]=max(num[n[a]],a)
nums=[]
for i in range(8):
    if num[i]: nums.append((i,num[i]))
#print(nums)
dp=[0]*(N+1)
for x,y in nums:
    dp[x]=1
for i in range(nums[0][0]+1,N+1):
    t=dp[i]
    for x,y in nums:
        if i-x>0:
            if dp[i-x]:
                t=max(t,dp[i-x]+1)
    if t:dp[i]=t
#print(dp)
nums.sort(key=lambda x:-x[1])
match=N
digit=dp[N]
for _ in range(dp[N]):
    if digit==1:
        for x,y in nums:
            if x==match:
                print(y)
                break
        break
    for x,y in nums:
        if dp[match-x]==digit-1:
            print(y,end='')
            match-=x
            digit-=1
            break

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
listA = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
dp = [-1]*N
dp[0] = 0
for j in range(1, N+1):
	for a in listA:
		if j-c[a] >= 0:
			dp[j] = max(dp[j], dp[j-c[a]]*10+a)
print(dp[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A.sort(reverse = True)

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