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

Solution (Python):

import sys







"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        
        
        
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    a = ip.IL()
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]  
    f = [0] + [-1] * 10000  

    
    for i in r(n):
        
        i += 1
        for x in a:
            
            
            o = c[x]  
            
            if i - o >= 0:  
                
                f[i] = max(f[i], f[i - o] * 10 + x)

    print(f[n])


main()

Solution (Python):
N,M = map(int, input().split())
A = list(map(int, input().split()))
dp = [None]*(N+1)
dp[0] = ""
f = [-1, 2,5,5,4,5,6,3,7,6] 

def max_str(s1:str, s2:str)->str:
    """return bigger one"""
    l1, l2 = len(s1), len(s2)
    if l1 != l2:
        return s1 if l1>l2 else s2
    if l1 == l2: 
        return s1 if s1>s2 else s2
    
for i in range(2, N+1):
    nxt = ""
    for aj in A:
        if i-f[aj]<0 or dp[i-f[aj]]==None: continue
        nxt = max_str(nxt, 
                      dp[i-f[aj]]+str(aj))
    if nxt!="":
        dp[i] = nxt
    
print(dp[N])

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

inf = float("inf")
dp = [-inf for i in range(n+1)]
dp[0] = 0

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

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

a.sort(reverse=True)
ans = ""
while n > 0:
    for i in a:
        state = True
        if n-cost[i] >= 0 and dp[n-cost[i]] == dp[n]-1:
            ans += str(i)
            n -= cost[i]
            state = False
            break
    if state:
        break

if ans == "":
    print(0)
else:
    print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


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



N, M = 0, 0
A = [0]


def hoge():
    d = dict()
    def labeler(label, iter):
        enumerate()


def set_inputs():
    global N, M, A
    N, M = get_int_list()
    A = get_int_list()


@lru_cache(maxsize=None)
def dp(i):
    if i < 0:
        return -inf
    elif i == 0:
        return 0
    return max(dp(i - COST[a]) + 1 for a in A)


def main():
    setrecursionlimit(100000)
    set_inputs()

    candidates = sorted(A, reverse=True)
    ret = []
    n = N
    for i in range(dp(N)):
        for a in candidates:
            cond = True
            if i == dp(N) - 1:
                cond = COST[a] == n
            if dp(n - COST[a]) == dp(n) - 1 and cond:
                ret.append(a)
                n -= COST[a]
                break
    print(''.join(str(r) for r in ret))


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int, input().split())  
A=list(map(int, input().split()))  
num = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

A.sort(reverse=True)    

dp = [-1*float("inf")]*(n+1)    

dp[0] = 0
for a in A:
    if num[a] <= n:
        dp[num[a]] = 1

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

ans = ""
for i in range(dp[n]):  
    for a in A: 
        if n-num[a] >= 0 and dp[n-num[a]] == dp[n]-1:
            ans += str(a)
            n -= num[a]
            break
 
print(ans)

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5 ,6, 3, 7, 6]
dp = ["" for i in range(N+30)]
for i in range(N):
    if i!=0 and dp[i]=="":
        continue
    for a in A:
        tmpscore = dp[i]+str(a)
        if len(dp[i+num[a]]) < len(tmpscore):
            dp[i+num[a]] = tmpscore
        elif len(dp[i+num[a]]) > len(tmpscore):
            continue
        else:
            dp[i+num[a]] = max(dp[i+num[a]], tmpscore)
print(dp[N])

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5 ,6, 3, 7, 6]
dp = ["" for i in range(50000)]
for i in range(N):
    if i!=0 and dp[i]=="":
        continue
    for a in A:
        if dp[i+num[a]] == "":
            dp[i+num[a]] = dp[i] + str(a)
        else:
            tmpscore = dp[i]+str(a)
            if len(dp[i+num[a]]) < len(tmpscore):
                dp[i+num[a]] = tmpscore
            elif len(dp[i+num[a]]) > len(tmpscore):
                continue
            else:
                dp[i+num[a]] = max(dp[i+num[a]], tmpscore)
print(dp[N])

Solution (Python):

import sys








"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        
        
        
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""
    n, m = ip.IL()
    a = ip.IL()
    c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    f = [-1] * 10010
    f[0] = 0

    for i in r(n):
        i += 1
        for x in a:
            if i - c[x] >= 0:
                f[i] = max(f[i], f[i - c[x]] * 10 + x)

    print(f[n])


main()

Solution (Python):
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 = [-1*float("inf")]*(N+1)

dp[0] = 0
for a in A:
    if num[a] <= N:
        dp[num[a]] = 1

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

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

print(ans)

Solution (Python):
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i-j < 0:
            pass
        elif i == j:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

ans = ''
ans_digit = dp[n]
while len(ans) < ans_digit:
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                ans += str(i)
                break
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    n -= dic[i]
                    break
    
print(ans)

Solution (Python):
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 = [-1*float("inf")]*(N+1000)

dp[0] = 0
for a in A:
    dp[num[a]] = 1

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

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

print(ans)

Solution (Python):
costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        if max(arr) < 0:
            continue

        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>0:
        arr = [ a for a in A if n-costs[a-1] >= 0 and D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        
        
    print(ans)

main()

Solution (Python):

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

cost = [0,2,5,5,4,5,6,3,7,6]
A =list(map(int, input().split()))
dp = [-1]*(N+1)
dp[0] = 0

for i in range(N):
    if dp[i] == -1:
        continue
    for c,a in zip( [cost[a] for a in A], A):
        if i + c <= N:
            dp[i+c] = dp[i]+1


i = N
ans = ""
A = sorted(A, reverse=True)
while i > 0:
    for c,a in zip([cost[a] for a in A], A):
        if i-c >= 0 and dp[i-c] == dp[i]-1:
            ans += str(a)
            i -= c
            break 

print(ans)

Solution (Python):

"""
Created on Sat Feb 16 19:31:10 2019
ABC118D
@author: maezawa
"""
import copy

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort(reverse=True)

nmatch = [2,5,5,4,5,6,3,7,6]
rmatch = list(reversed(nmatch))
nmdic = dict([(i+1,nmatch[i]) for i in range(9)])

nums = [[] for _ in range(10)]
for  i in a:
    nums[nmdic[i]].append(i)
        



dp = [[-1,[]] for _ in range(n+1)]
dp[0] = [0, []]


for i in range(1, n+1):
    cnds = []
    for k in a:
        j = nmdic[k]
        if i-j < 0:
            continue
        if dp[i-j][0] == -1:
            continue
        cndo = dp[i-j][0]+1
        cndos = copy.copy(dp[i-j][1])
        cndos.append(max(nums[j]))
        cnds.append([cndo, cndos])
        
    if cnds == []:
        continue
    dp[i] = max(cnds, key=lambda x: x[0])

ans = ''.join(map(str, sorted(dp[n][1], reverse=True)))
print(ans)

Solution (Python):
import numpy as np


nmatch = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
dp = [-1]*(N+1) 
dp[0] = 0
ff = np.array(list(map(int,input().split()))).reshape(-1,1)
fg = nmatch[ff].reshape(-1,1)
Atemp = np.concatenate([ff,fg],axis=1)
index0 = np.argsort(Atemp[:,0])
index1 = np.argsort(Atemp[:,1])
A = Atemp[index1] 
B = Atemp[index0]
B = B[::-1] 
for i in range(1,N+1):
    for k in range(M):
        j = A[k,1]
        i_old = i - j 
        if (i-j) < 0:
            break
        if (i-j) == 0 and dp[i] == -1:
            dp[i] = 1
        if dp[i_old] != -1 and dp[i_old]+1 > dp[i]:
            dp[i] = dp[i_old] + 1

ndigits = dp[N]
j = N
final_number = ''
for l in range(ndigits,0,-1):
    index = 0
    while True:
        temp_j = j - B[index,1]
        if temp_j < 0:
            index += 1
            continue
        if dp[temp_j] + 1 == dp[j]:
            final_number += str(B[index,0])
            j = temp_j
            break
        else:
            index += 1
        if index > M:
            break
print(int(final_number))

Solution (Python):
from collections import defaultdict
from copy import copy

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

ms = [2,5,5,4,5,6,3,7,6]
dic = defaultdict(lambda: 0)
for a in A:
    dic[ms[a-1]] = max(dic[ms[a-1]], a)

sd = sorted(dic.items())

dp = [None] * (N+1)
dp[0] = defaultdict(lambda: 0)

for i in range(sd[0][0], N+1):
    cands = []
    least_len = -1
    for l,a in sd:
        if i-l < 0: break
        if dp[i-l] is None: continue
        if cands and sum(dp[i-l].values())+1 < least_len:
            continue
        cands.append(copy(dp[i-l]))
        cands[-1][a] += 1
        least_len = sum(cands[-1].values())
    if not cands: continue
    max_v = 0
    max_j = -1
    for j,cand_dic in enumerate(cands):
        tmp_s = ''
        for a,n in sorted(cand_dic.items(), reverse=True):
            tmp_s += str(a) * n
        tmp_v = int(tmp_s)
        if tmp_v > max_v:
            max_v = tmp_v
            max_j = j
    dp[i] = cands[max_j]

ans = ''
for a,n in sorted(dp[-1].items(), reverse=True):
    ans += str(a) * n
print(ans)

Solution (Python):
cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

''' 再帰が深すぎて, 再起不能
def solve(yoshida, possible, dp):
    if(yoshida == 0):
        dp[0] = 0
    elif(dp[yoshida] == -1):
        for x in possible:
            if(yoshida >= cost[x]):
                idx = yoshida - cost[x]
                solve(idx, possible, dp)
                a = (dp[idx]) * 10 + x
                dp[yoshida] = max(dp[yoshida], a)
'''

def solve(yoshida, possible, dp):
    dp[0] = 0
    for i in range(n):
        a = 10 * dp[i]
        for x in possible:
            dp[i + cost[x]] = max(dp[i + cost[x]], a + x)
if __name__ == '__main__':
    n, m = map(int, input().split())
    lst = list(map(int, input().split(" ")))
    DP = [-1] * (n + 10)
    solve(n, lst, DP)
    '''
    for i in range(n + 1):
        print("{} : {}".format(i, DP[i]))
    '''
    print(DP[n])

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

dp = [0 for i in range(0, n + 1)]
s = [0 for i in range(0, n + 1)]
b = [0 for i in range(0, n + 1)]

c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
a.sort()
a = a[::-1]

for i in range(1, n + 1):
    l = -1
    argl = 0
    pl = 0
    for j in range(0, m):
        p = i - c[a[j]]
        if p >= 0 and dp[p] > l:
            l = dp[p]
            argl = j
            pl = p
    if l < 0:
        dp[i] = -1
    else:
        dp[i] = l + 1
        s[i] = a[argl]
        b[i] = pl

bi = n
u = ""
while bi > 0:
    u += str(s[bi])
    bi = b[bi]

print(u)

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = ["-"] * (N + 10000)

dp[0] = ""


def max_str(s, t):
    if s == "-":
        return t
    elif len(s) < len(t):
        return t
    elif len(s) == len(t):
        if s < t:
            return t
        else:
            return s
    else:
        return s


for i in range(N + 1):
    if dp[i] == "-":
        continue
    for a in a_list:
        dp[i + items[a]] = max_str(dp[i + items[a]], dp[i] + str(a))

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = {}
for i in range(N + 1):
    x = 0
    for j in A:
        k = num[j - 1]
        if i - k < 0:
            continue
        if i == k:
            x = max(x, j)
            continue
        an = ans[i - k]
        if an == 0:
            continue
        x = max(x, an * 10 + j)
    ans[i] = x
print(ans[N])

Solution (Python):
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[-1])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
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())

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

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

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        use[dic[ai]] = max(use[dic[ai]], ai)
        

desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        

INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    cand = dp[i].copy()
    for idx in range(len(use)):
        if i - edge[idx] < 0:
            continue

        if sum(cand) < sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            cand = tmp.copy()
            

        elif sum(cand) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(cand, tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    cand = tmp.copy()
                    break
                
    dp[i] = cand
                

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)

Solution (Python):
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
num = [0,2,5,5,4,5,6,3,7,6] 

D = {} 
for i in range(M):
  n = num[A[i]]
  if D.get(n):
    D[n] = max(D[n], A[i])
  else:
    D[n] = A[i]


DP = [(-1, -1)]*(N+1) 
DP[0] = (0, 0)
for i in range(N+1):
  for key in D:
    if i - key >= 0 and DP[i-key] != -1:
      temp = (DP[i-key][0] + 1, max(DP[i-key][1], D[key]))
      DP[i] = max(DP[i], temp)


ans = ''
now = N
while now > 0:
  ans += str(DP[now][1])
  now = now - num[DP[now][1]]
print(ans)

Solution (Python):
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
num = [0,2,5,5,4,5,6,3,7,6] 
D = {}
for i in range(M):
  n = num[A[i]]
  if D.get(n):
    D[n] = max(D[n], A[i])
  else:
    D[n] = A[i]

DP = [(-1, -1)]*(N+1)
DP[0] = (0, 0)
for i in range(N+1):
  for key in D:
    if i - key >= 0 and DP[i-key] != -1:
      temp = (DP[i-key][0] + 1, max(DP[i-key][1], D[key]))
      DP[i] = max(DP[i], temp)

ans = ''
now = N
while now > 0:
  ans += str(DP[now][1])
  now = now - num[DP[now][1]]
print(ans)

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10for j in a)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]+[-1]*n*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10for j in a)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10for j in a)
print(d[n])

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

can_use = [False for i in range(10)]
for a in A:
    can_use[a] = True

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

dp = [-1 for i in range(10 ** 4 + 1)]
dp[0] = 0

for i in range(N):
    if dp[i] < 0:
        continue
    for d in range(1, 10):
        if can_use[d] and i + match[d] <= N:
            dp[i + match[d]] = max(dp[i + match[d]], dp[i] * 10 + d)

print(dp[N])

Solution (Python):
n,m,*a=map(int,open(0).read().split());d=[0]*n+[-1]*9
for i in range(n):d[i+1]=max(d[i-int("0144345265"[j])]*10+j for j in a)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(n):d[i+1]=max(d[i-int("0144345265"[j])]*10+j for j in a)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n+[-1]*9
for i in range(1,n+1):d[i]=max(d[i-int("0255456376"[j])]*10+j for j in a)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9+[-1]*n*9
for i in range(1,n+1):d[i]=max(d[i-int("0255456376"[j])]*10+j for j in a)
print(d[n])

Solution (Python):
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

As.sort(reverse=True)


dp = [[-float('inf')]*(N+1) for _ in range(M+1)]
dp[0][0] = 0
for i, A in enumerate(As, 1):
    for j in range(N+1):
        dp[i][j] = dp[i-1][j]
        if j >= nums[A]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-nums[A]]*10+A, dp[i][j-nums[A]]*10+A)

print(dp[-1][-1])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:c=i+int("0255456376"[j]);d[c]=max(d[c],(d[i]*10+j)*(i<1or d[i]>0))
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split());d=[0]*n*9
for i in range(n):
 for j in a:
  if d[i]or i<1:c=i+int("0255456376"[j]);d[c]=max(d[c],d[i]*10+j)
print(d[n])

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

dp = [[-1 for i in range(10)] for j in range(N+1)]

B = [0 for i in range(10)]
C = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
for i in range(10):
    if i in A:
        B[i] = C[i]

for i in range(10):
    dp[N][i] = 0
    
for i in range(N, -1, -1):
    for j in range(10):
        for k in range(j+1):
            if B[k] > 0 and i+B[k] <= N:
                
                dp[i][k] = max(dp[i][k], dp[i+B[k]][j] * 10 + k)


                
ans = 0
for i in range(10):
    ans = max(ans, dp[0][i])

print(ans)

Solution (Python):
import time
n, m = map(int, input().split())
numbers = list(map(int, input().split()))
costs = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0] = 0
for i in range(1, n+1):
    for x in numbers:
        if i-costs[x] >= 0:
            f[i] = max(f[i], f[i-costs[x]]*10+x)
print(f[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:c=i+(0,2,5,5,4,5,6,3,7,6)[j];d[c]=max(d[c],(d[i]*10+j)*(i<1or d[i]>0))
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:
  if d[i]or i<1:c=i+(0,2,5,5,4,5,6,3,7,6)[j];d[c]=max(d[c],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]*n*9
for i in range(n):
 for j in a:
  c=(0,2,5,5,4,5,6,3,7,6)[j]
  if d[i]or i<1:d[i+c]=max(d[i+c],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
c=(0,2,5,5,4,5,6,3,7,6)
d=[0]*n*9
for i in range(n):
 for j in a:
  c=(0,2,5,5,4,5,6,3,7,6)[j]
  if d[i]or i<1:d[i+c]=max(d[i+c],d[i]*10+j)
print(d[n])

Solution (Python):

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

cost = [0,2,5,5,4,5,6,3,7,6]
A =list(map(int, input().split()))
dp = [-1]*(N+1)
dp[0] = 0

for i in range(N):
    if dp[i] == -1:
        continue
    for c,a in zip( [cost[a] for a in A], A):
        if i + c <= N:
            dp[i+c] = dp[i]+1


i = N
ans = ""
A = sorted(A, reverse=True)
while i > 0:
    for c,a in zip([cost[a] for a in A], A):
        if i-c >= 0 and dp[i-c] == dp[i]-1:
            ans += str(a)
            i -= c
            break 

print(ans)

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




a.sort()
table = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

dp = ["" for i in range(max(n + 1, m+1))]
for x in a:
    dp[table[x]] = str(x)


def str_max(maxstrs):
    maxstrlen = max(map(lambda x:len(x), maxstrs))
    maxstr = max(filter(lambda x:len(x) == maxstrlen, maxstrs))
    return maxstr


for i in range(n + 1):
    for x in a:
        tmpstr = str(x)
        tmprest = i - table[x]
        if tmprest < 0:
            tmpstr = ""
        if 0 <= tmprest:
            
            tmp = dp[tmprest]
            if tmp == "":
                tmpstr = ""
            else:
                tmpstr = tmp + str(x)
        dp[i] = str_max([dp[i], tmpstr])

print(dp[n])

Solution (Python):
n,m=map(int,input().split())
A=list(input().split())
c=[0,2,5,5,4,5,6,3,7,6]

dp=['']*(n+1)
dp[0]=''
for i in range(1,n+1):
    max=''
    for j in range(m):
        if (i-c[int(A[j])]>0 and dp[i-c[int(A[j])]]!='') or (i-c[int(A[j])]==0):
            if len(dp[i-c[int(A[j])]]+A[j])>len(max):
                max=dp[i-c[int(A[j])]]+A[j]
            elif len(dp[i-c[int(A[j])]]+A[j])==len(max) and dp[i-c[int(A[j])]]+A[j]>max:
                max=dp[i-c[int(A[j])]]+A[j]
    dp[i]=max
print(dp[n])