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):
def inv(x, ava):
    if x == 2:
        if 1 in ava:
            return 1
        else:
            return -1
    if x == 3:
        if 7 in ava:
            return 7
        else:
            return -1
    if x == 4:
        if 4 in ava:
            return 4
        else:
            return -1
    if x == 5:
        if 5 in ava:
            return 5
        if 3 in ava:
            return 3
        if 2 in ava:
            return 2
        else:
            return -1
    if x == 6:
        if 9 in ava:
            return 9
        if 6 in ava:
            return 6
        else:
            return -1
    if x == 7:
        if 8 in ava:
            return 8
        else:
            return -1
n, m = map(int, input().split())
ava = list(map(int, input().split()))
dp = [[] for _ in range(n+1)]
number = [inv(x,ava) for x in range(2,8)]
avapre = []
for i in range(6):
    if number[i] != -1:
        avapre.append(i+2)
avapresort = sorted(avapre,key = lambda x: number[x-2],reverse=True)
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):
    if i < avapre[0]:
        dp[i] = -1
    else:
        dp[i] = -1
        for pre in avapre:
            if i - pre >= 0:
                dp[i] = max(dp[i], dp[i-pre]+1)
i = n
while(i > 0):
    for pre in avapresort:
        if i - pre >= 0 and dp[i] == dp[i-pre] + 1:
            print(number[pre-2], end='')
            i -= pre
            break
print()

Solution (Python):
def inv(x, ava):
    if x == 2:
        if 1 in ava:
            return 1
        else:
            return -1
    if x == 3:
        if 7 in ava:
            return 7
        else:
            return -1
    if x == 4:
        if 4 in ava:
            return 4
        else:
            return -1
    if x == 5:
        if 5 in ava:
            return 5
        if 3 in ava:
            return 3
        if 2 in ava:
            return 2
        else:
            return -1
    if x == 6:
        if 9 in ava:
            return 9
        if 6 in ava:
            return 6
        else:
            return -1
    if x == 7:
        if 8 in ava:
            return 8
        else:
            return -1
n, m = map(int, input().split())
ava = list(map(int, input().split()))
dp = [[] for _ in range(n+1)]
number = [inv(x,ava) for x in range(2,8)]
avapre = []
for i in range(6):
    if number[i] != -1:
        avapre.append(i+2)
avapresort = sorted(avapre,key = lambda x: number[x-2],reverse=True)
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):
    if i < avapre[0]:
        dp[i] = -1
    else:
        dp[i] = -1
        for pre in avapre:
            if i - pre >= 0:
                dp[i] = max(dp[i], dp[i-pre]+1)
i = n
while(i > 0):
    for pre in avapresort:
        if i - pre >= 0 and dp[i] == dp[i-pre] + 1:
            print(number[pre-2], end='')
            i -= pre
            break
print()

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
can_cost = sorted([cost[a] for a in A])
D = {}
for a in A:
    c = cost[a]
    D[c] = max(a, D.setdefault(c, -1))

min_cost = can_cost[0]
min_cost_num = D[min_cost]


def f2(v, l, num):
    L = list(str(v))
    min_cost = cost[int(num)]
    num = D.setdefault(min_cost + l, -1)
    if num == -1:
        return -1

    min_cost_num = D[min_cost]
    L[L.index(str(min_cost_num))] = str(num)
    L.sort(reverse=True)
    return int("".join(L))


def f(v, l):
    L = list(str(v))
    set_L = set(L)
    L2 = [f2(v, l, num) for num in set_L]
    return max(L2)

def g(K, r):
    temp = int("".join([str(min_cost_num)] * K))
    dp = [[-1 for _ in range(min(r, K) + 1)] for __ in range(r + 1)]
    dp[0][0] = temp

    for k in range(min(r, K)):
        for n in range(r):
            v = dp[n][k]
            if v == -1:
                continue
            for l in range(1, r - n + 1):
                dp[n + l][k + 1] = max(dp[n + l][k + 1], f(v, l))
    return max(dp[r])

K = N // min_cost
r = N - K * min_cost
res = g(K, r)
if g(K, r) == -1:
    res = g(K - 1, r + min_cost)
print(res)

Solution (Python):


N, M = map(int, input().split())
A = [int(a) for a in input().split()]    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]
best = sorted(B, key = lambda x: x[1]*10-x[0])[0]
adj = max((N - 200),0)//best[1]
N -= best[1] * adj

X = [0] + [-10**9] * N
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                X[i] = max(X[i], X[i-b[1]]*10 + b[0])

ans = str(X[N])
ans = ans[:10] + str(best[0]) * adj + ans[10:]

print(ans)

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

Solution (Python):



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

n,mmm = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


bar = list(set([table[i] for i in a]))
bar.sort()
minbar=min(bar)

maxnum = ['0']*10
for i in bar:
    mbmax = max([j for j in a if table[j] == i])
    maxnum[i]=str(mbmax)

ans = ['0']*(100)
for i in range(8):
    if i in bar:
        ans[i]=maxnum[i]

for i in range(90):
    if ans[i] == '0':
        continue
    for j in bar:
        if maxnum[j] > ans[i][0]:
            tmp = maxnum[j]+ans[i]
        else:
            tmp = ans[i]+maxnum[j]
            ans[i+j] = str(max(int(ans[i+j]),int(tmp)))

if n < 90:
    print(ans[n])
else:
    mn = maxnum[minbar]
    ans2=0
    for i in range(90):
        if n>=i and (n-i)%minbar == 0:
            q=(n-i)//minbar
            if ans[i]=='0' : continue
            X = ''.join([j for j in ans[i] if j > mn])
            Y = ''.join([j for j in ans[i] if j <= mn])
            tmp = int(X+str(mn)*q+Y)

            ans2 = str(max(int(ans2),tmp))
    print(ans2)

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

Solution (Python):
n,m=map(int,input().split())
dp=[0]+[-(2**30) for i in range(n)]
a,b=sorted(list(map(int,input().split())),reverse=True),[0,2,5,5,4,5,6,3,7,6]
for i in range(n):
	for j in range(m):
		if(i+b[a[j]]>n):
			continue
		dp[i+b[a[j]]] = max(dp[i+b[a[j]]],dp[i]+1)
ans = ""
while n:
	for j in range(m):
		if n-b[a[j]]<0:
			continue
		if dp[n-b[a[j]]] == dp[n]-1:
			ans += str(a[j])
			n -= b[a[j]]
			break
print(ans)

Solution (Python):
import math
import copy
import bisect







def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input().split())
m=nCast(input().split())

def cmp(l1,l2):

    if len(l1)!=len(l2):
        return len(l1)-len(l2)
    for idx in range(len(l1)-1,0,-1):
        if l1[idx]!=l2[idx]:
            return l1[idx]-l2[idx]
    return 0
def func():
    l=list()
    nn=[1,2,3,4,5,6,7,8,9]
    s=set(m)
    mm=[2,5,5,4,5,6,3,7,6]
    d=dict()
    for idx in nn:
        if idx in s:
            if idx==2 and 5 in s:
                continue
            if idx==3 and 5 in s:
                continue
            if idx==2 and 3 in s:
                continue
            if idx==6 and 9 in s:
                continue
            d[nn[idx-1]]=mm[idx-1]
    for idx in range(0,n[0]+1):
        l.append(list())
    for idx in range(1,n[0]+1):
        for idy in d:
            if idx-d[idy]>0:
                tmp=l[idx-d[idy]][:]
                if len(tmp)==0:
                    continue
                tmp.append(idy)
                
                if cmp(tmp,l[idx])>0:
                    l[idx]=tmp
            elif idx-d[idy]==0:
                max=0
                for dd in d:
                    if d[dd]==idx and dd>max:
                        max=dd
                if cmp([max],l[idx])>0:
                    l[idx]=[max]

    result=""
    l[-1].sort(reverse=True)
    for idx in range(0,len(l[-1])):
        result=result+str(l[-1][idx])
    return result



print(func())

Solution (Python):
num = [0,2,5,5,4,5,6,3,7,6]
n, m = map(int, input().split())
dp = [-1] * (n+10)
a = list(map(int, input().split()))
a.sort()
a.reverse()
b = list()
for x in a:
    b.append(num[x])
dp[0] = 0
for i in range(n):
    for x in b:
        dp[i+x] = max(dp[i+x], dp[i] + 1)
ans = str()
while n > 0:
    for i in range(m):
        if n-b[i] >= 0 and dp[n] == dp[n-b[i]] + 1:
            n -= b[i]
            ans += str(a[i])
            break
print(ans)

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

if enabled[1]:
    if n % 2 == 1:
        if enabled[7]:
            res = "7" + ((n - 3) // 2) * "1"
        elif enabled[5]:
            res = "5" + ((n - 5) // 2) * "1"
        elif enabled[3]:
            res = "3" + ((n - 5) // 2) * "1"
        elif enabled[2]:
            res = "2" + ((n - 5) // 2) * "1"
        else:
            res = "8" + ((n - 7) // 2) * "1"
    else:
        res = "1" * (n // 2)
elif enabled[7]:
    if n % 3 == 1:
        if enabled[4]:
            res = "7" * ((n - 4) // 3) + "4"
        elif enabled[8]:
            res = "8" + "7" * ((n - 7) // 3)
        elif enabled[5]:
            res = "7" * ((n - 10) // 3) + "55"
        elif enabled[3]:
            res = "7" * ((n - 10) // 3) + "33"
        elif enabled[2]:
            res = "7" * ((n - 10) // 3) + "22"
    elif n % 3 == 0:
        res = "7" * (n // 3)
    else:
        if enabled[5]:
            res = "7" * ((n - 5) // 3) + "5"
        elif enabled[3]:
            res = "7" * ((n - 5) // 3) + "3"
        elif enabled[2]:
            res = "7" * ((n - 5) // 3) + "2"
        elif enabled[4]:
            res = "7" * ((n - 8) // 3) + "44"
        elif enabled[8]:
            res = "88" + "7" * ((n - 14) // 3)
elif enabled[4]:
    if n % 4 == 0:
        res = "4" * (n // 4)
    elif n % 4 == 1:
        if enabled[5]:
            res = "5" + "4" * ((n - 5) // 4)
        elif enabled[3]:
            res = "4" * ((n - 5) // 4) + "3"
        elif enabled[2]:
            res = "4" * ((n - 5) // 4) + "2"
        elif enabled[8]:
            if enabled[9]:
                res = "98" + ((n - 13) // 4) * "4"
            elif enabled[6]:
                res = "86" + ((n - 13) // 4) * "4"
            else:
                res = "888" + ((n - 21) // 4) * "4"
    elif n % 4 == 2:
        if enabled[9]:
            res = "9" + "4" * ((n - 6) // 4)
        elif enabled[6]:
            res = "6" + "4" * ((n - 6) // 4)
        elif enabled[5]:
            res = "55" + "4" * ((n - 10) // 4)
        elif enabled[3]:
            res = "4" * ((n - 10) // 4) + "33"
        elif enabled[2]:
            res = "4" * ((n - 10) // 4) + "22"
        elif enabled[8]:
            res = "88" + ((n - 14) // 4) * "4"
    else:
        if enabled[9]:
            if enabled[5]:
                res = "95" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "9" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "9" + "4" * ((n - 11) // 4) + "2"
        elif enabled[8]:
            res = "8" + "4" * ((n - 7) // 4)
        elif enabled[6]:
            if enabled[5]:
                res = "65" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "6" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "6" + "4" * ((n - 11) // 4) + "2"
        elif enabled[5]:
            res = "555" + "4" * ((n - 15) // 4)
        elif enabled[3]:
            res = "4" * ((n - 15) // 4) + "333"
        else:
            res = "4" * ((n - 15) // 4) + "222"
else:
    for i in [5, 3, 2]:
        c = str(i)
        if enabled[i]:
            if n % 5 == 0:
                res = c * (n // 5)
            elif n % 5 == 1:
                if enabled[9]:
                    res = "9" + c * ((n - 6) // 5)
                elif enabled[6]:
                    res = "6" + c * ((n - 6) // 5)
                else:
                    res = "888" + c * ((n - 21) // 5)
            elif n % 5 == 2:
                if enabled[9]:
                    res = "99" + c * ((n - 12) // 5)
                elif enabled[8]:
                    res = "8" + c * ((n - 7) // 5)
                else:
                    res = "66" + c * ((n - 12) // 5)
            elif n % 5 == 3:
                if enabled[9]:
                    res = "999" + c * ((n - 18) // 5)
                elif enabled[6]:
                    if enabled[8]:
                        res = "86" + c * ((n - 13) // 5)
                    else:
                        res = "666" + c * ((n - 18) // 5)
                else:
                    res = "8888" + c * ((n - 28) // 5)
            else:
                if enabled[9]:
                    res = "9999" + c * ((n - 24) // 5)
                elif enabled[8]:
                    res = "88" + c * ((n - 14) // 5)
                else:
                    res = "6666" + c * ((n - 24) // 5)
            print(res)
            exit()
    if enabled[9]:
        if n % 6 == 0:
            res = "9" * (n // 6)
        elif n % 6 == 1:
            res = "9" * ((n - 7) // 6) + "8"
        elif n % 6 == 2:
            res = "9" * ((n - 14) // 6) + "88"
        elif n % 6 == 3:
            res = "9" * ((n - 21) // 6) + "888"
        elif n % 6 == 4:
            res = "9" * ((n - 28) // 6) + "8888"
        else:
            res = "9" * ((n - 35) // 6) + "88888"
    elif enabled[6]:
        if n % 6 == 0:
            res = "6" * (n // 6)
        elif n % 6 == 1:
            res = "8" + "6" * ((n - 7) // 6)
        elif n % 6 == 2:
            res = "88" + "6" * ((n - 14) // 6)
        elif n % 6 == 3:
            res = "888" + "6" * ((n - 21) // 6)
        elif n % 6 == 4:
            res = "8888" + "6" * ((n - 28) // 6)
        else:
            res = "88888" + "6" * ((n - 35) // 6)
    else:
        res = "8" * (n // 7)
print(res)

Solution (Python):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]
best = sorted(B, key = lambda x: x[1]*10-x[0])[0]
adj = max((N - 200),0)//best[1]
N -= best[1] * adj

X = [0] + [-10**9] * N
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                X[i] = max(X[i], X[i-b[1]]*10 + b[0])

ans = str(X[N])
ans = ans[:10] + str(best[0]) * adj + ans[10:]

print(ans)

Solution (Python):
tmp = [0] * 10
def rec(i):
  for j in range(len(w)):
    if(i >= w[j] and dp[0][ i - w[j] ] != -1):
      if(dp[0][ i - w[j] ] + 1 > dp[0][i]):
        dp[0][i] = dp[0][ i - w[j] ] + 1
        for k in range(10):
          dp[1][i][k] = dp[1][ i - w[j] ][k]
        dp[1][i][v[j]] += 1

      elif(dp[0][ i - w[j] ] + 1 == dp[0][i]):
        for k in range(10):
          tmp[k] = dp[1][ i - w[j] ][k]
        tmp[v[j]] += 1
        for k in range(9,0,-1):
          if(tmp[k] > dp[1][i][k]):
            dp[0][i] = dp[0][ i - w[j] ] + 1
            for k in range(10):
              dp[1][i][k] = dp[1][ i - w[j] ][k]
            dp[1][i][v[j]] += 1
            break
          elif(tmp[k] < dp[1][i][k]):
            break

n, k = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
ww = [2,5,5,4,5,6,3,7,6]
z =  [1,7,4,5,3,2,9,6,8]

dp = [0]*2
dp[0] = [-1] * (n+1)
dp[0][0] = 0
dp[1] = [ [0 for i in range(10)] for j in range(n+1)]
w = []
v = []
for i in z:
  if(i in a):
    if(not ww[i-1] in w):
      v.append(i)
      w.append(ww[i-1])

for i in range(min(w), n+1):
  rec(i)

for i in range(9,0,-1):
  print("{}".format(i)*dp[1][n][i], end='')

Solution (Python):
nums = list(map(int, input().split()))
N, M = nums[0], nums[1]
A = list(map(int, input().split()))

nums = [2,5,5,4,5,6,3,7,6];

from copy import deepcopy as copy
dp = [[0 for _ in range(10)] for _ in range(N+1)]

def compare_dp(a1, a2):
    for i in range(10):
        if a1[i] > a2[i]:
            return True
        elif a1[i] < a2[i]:
            return False

    return True

def allzero(a):
    flag = True
    for e in a:
        flag = flag and (e==0)
    return flag

for i in range(N+1):
    for j in range(M):
        if i >= nums[A[j]-1]:
            if (not allzero(dp[i-nums[A[j]-1]])) or i-nums[A[j]-1]==0:
                val = copy(dp[i-nums[A[j]-1]])
                val[0] += 1
                val[10-A[j]] += 1
                if compare_dp(val, dp[i]):
                    dp[i] = copy(val)

for i in range(9):
    for j in range(dp[N][i+1]):
        print(9-i, end="")
print("\n", end="")

Solution (Python):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = max((N - 200),0)//best[1]
N -= best[1] * adj

X = [0] + [-10**9] * N
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0])

ans = str(X[N])
if adj > 0:
    ans = ans[:10] + str(best[0]) * adj + ans[10:]

print(ans)

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

setnum = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6} 
rset = {}
for i in a:
    if i in rset:
        if rset[setnum[i]] > i:
            rset[i] = setnum[i]
    else:
        rset[i] = setnum[i]

rset = sorted(rset.items(), reverse=True)
dp = [0] * (n + 1)
for i in rset:
    if n < i[1]:
        continue
    dp[i[1]] = max(dp[i[1]] , i[0])
    for j in range(i[1], n + 1 - i[1]):
        if dp[j] != 0:
            dp[j + i[1]] = max(dp[j + i[1]], dp[j] * 10 + i[0])
print(dp[-1])

Solution (Python):
N , M = map(int,input().split())
L = sorted(list(map(int,input().split())))
table =  [0,2,5,5,4,5,6,3,7,6]
L_val =sorted( list(map(lambda x:(table[x],x),L)))
number = ["0" for i in range(10**4+10)]

def comp(x,y):
    if len(x) >len(y):
        return 0
    elif len(x) < len(y):
        return 1
    else:
        for i in range(len(x)):
            if x[i] == y[i]:
                i+=1
            elif int(x[i]) < int(y[i]):
                return 1
            elif int(x[i]) > int(y[i]):
                return 0
        return 0



for x in L_val:
    number[x[0]] = str(x[1])

for i in range(10**4):
    tmp = number[i]
    if tmp=="0":
        continue
    for x in L_val:
        if  comp(number[i+x[0]],tmp + str(x[1])):
            number[i+x[0]] = tmp + str(x[1])

print(number[N])

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

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

min_w = 10
for i in a:
    min_w = min(min_w,w[i-1])

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


for i in range(0,n):
    if 1 <= i < min_w:
            dp[i] = -1
    for j in a:
        if i + 1 - w[j-1] >= 0 and dp[i + 1 - w[j-1]] != -1:
            dp[i+1] = max(dp[i+1],dp[i+1-w[j-1]]*10+j)
print(dp[n])

Solution (Python):

N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]

def check2(A,B):
    p = 0
    t = 0
    
    
    if len(A) > len(B):
        return A
    elif len(A) < len(B):
        return B
    for a,b in zip(A,B):
        if  a- b > 0:
            return A
        elif a-b < 0:
            return B
    return A
    
    
    
    
    
    

    
    

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check2(bagS[b+c[a]],sorted((bagS[b]+[a]),reverse=True))

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))

Solution (Python):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0])

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

print(ans)

Solution (Python):
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

n,m = map(int,input().split())

b = list(map(int,input().split()))
honsuu = [-1,2,5,5,4,5,6,3,7,6]
enabled = [False] * 10
for bb in b:
    enabled[bb] = True
if enabled[6] & enabled[9]:
     enabled[6] = False
if enabled[5] & (enabled[2] | enabled[3]):
     enabled[2] = enabled[3] = False
if enabled[2] & enabled[3]:
     enabled[2] = False
a = []
for i in range(10):
    if (enabled[i]):
        a.append(i)

if enabled[1]:
    if n % 2 == 1:
        if enabled[7]:
            res = "7" + ((n - 3) // 2) * "1"
        elif enabled[5]:
            res = "5" + ((n - 5) // 2) * "1"
        elif enabled[3]:
            res = "3" + ((n - 5) // 2) * "1"
        elif enabled[2]:
            res = "2" + ((n - 5) // 2) * "1"
        else:
            res = "8" + ((n - 7) // 2) * "1"
        print(res)
    else:
        print("1" * (n // 2))
    exit()

if enabled[7]:
    if n % 3 == 1:
        if enabled[4]:
            res = "7" * ((n - 4) // 3) + "4"
        elif enabled[8]:
            res = "8" + "7" * ((n - 7) // 3)
        elif enabled[5]:
            res = "7" * ((n - 10) // 3) + "55"
        elif enabled[3]:
            res = "7" * ((n - 10) // 3) + "33"
        elif enabled[2]:
            res = "7" * ((n - 10) // 3) + "22"
        print(res)
    elif n % 3 == 0:
        print("7" * (n // 3))
    else:
        if enabled[5]:
            res = "7" * ((n - 5) // 3) + "5"
        elif enabled[3]:
            res = "7" * ((n - 5) // 3) + "3"
        elif enabled[2]:
            res = "7" * ((n - 5) // 3) + "2"
        elif enabled[4]:
            res = "7" * ((n - 8) // 3) + "44"
        elif enabled[8]:
            res = "88" + "7" * ((n - 14) // 3)
        print(res)
    exit()

if enabled[4]:
    if n % 4 == 0:
        print("4" * (n // 4))
    elif n % 4 == 1:
        if enabled[5]:
            res = "5" + "4" * ((n - 5) // 4)
        elif enabled[3]:
            res = "4" * ((n - 5) // 4) + "3"
        elif enabled[2]:
            res = "4" * ((n - 5) // 4) + "2"
        elif enabled[8]:
            if enabled[9]:
                res = "98" + ((n - 13) // 4) * "4"
            elif enabled[6]:
                res = "86" + ((n - 13) // 4) * "4"
            else:
                res = "888" + ((n - 21) // 4) * "4"
        print(res)
    elif n % 4 == 2:
        if enabled[9]:
            res = "9" + "4" * ((n - 6) // 4)
        elif enabled[6]:
            res = "6" + "4" * ((n - 6) // 4)
        elif enabled[5]:
            res = "55" + "4" * ((n - 10) // 4)
        elif enabled[3]:
            res = "4" * ((n - 10) // 4) + "33"
        elif enabled[2]:
            res = "4" * ((n - 10) // 4) + "22"
        elif enabled[8]:
            res = "88" + ((n - 14) // 4) * "4"
        print(res)
    else:
        if enabled[9]:
            if enabled[5]:
                res = "95" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "9" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "9" + "4" * ((n - 11) // 4) + "2"
        elif enabled[8]:
            res = "8" + "4" * ((n - 7) // 4)
        elif enabled[6]:
            if enabled[5]:
                res = "65" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "6" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "6" + "4" * ((n - 11) // 4) + "2"
        elif enabled[5]:
            res = "555" + "4" * ((n - 15) // 4)
        elif enabled[3]:
            res = "4" * ((n - 15) // 4) + "333"
        else:
            res = "4" * ((n - 15) // 4) + "222"
        print(res)
    exit()

for i in [5, 3, 2]:
    c = str(i)
    if enabled[i]:
        if n % 5 == 0:
            print(c * (n // 5))
        elif n % 5 == 1:
            if enabled[9]:
                res = "9" + c * ((n - 6) // 5)
            elif enabled[6]:
                res = "6" + c * ((n - 6) // 5)
            else:
                res = "888" + c * ((n - 21) // 5)
            print(res)
        elif n % 5 == 2:
            if enabled[9]:
                res = "99" + c * ((n - 12) // 5)
            elif enabled[8]:
                res = "8" + c * ((n - 7) // 5)
            else:
                res = "66" + c * ((n - 12) // 5)
            print(res)
        elif n % 5 == 3:
            if enabled[9]:
                res = "999" + c * ((n - 18) // 5)
            elif enabled[6]:
                if enabled[8]:
                    res = "86" + c * ((n - 13) // 5)
                else:
                    res = "666" + c * ((n - 18) // 5)
            else:
                res = "8888" + c * ((n - 28) // 5)
            print(res)
        else:
            if enabled[9]:
                res = "9999" + c * ((n - 24) // 5)
            elif enabled[8]:
                res = "88" + c * ((n - 14) // 5)
            else:
                res = "6666" + c * ((n - 24) // 5)
            print(res)
        exit()

if enabled[9]:
    c = "9"
    if n % 6 == 0:
        print(c * (n // 6))
    elif n % 6 == 1:
        print(c * ((n - 7) // 6) + "8")
    elif n % 6 == 2:
        print(c * ((n - 14) // 6) + "88")
    elif n % 6 == 3:
        print(c * ((n - 21) // 6) + "888")
    elif n % 6 == 4:
        print(c * ((n - 28) // 6) + "8888")
    else:
        print(c * ((n - 35) // 6) + "88888")
    exit()

if enabled[6]:
    c = "6"
    if n % 6 == 0:
        print(c * (n // 6))
    elif n % 6 == 1:
        print("8" + c * ((n - 7) // 6))
    elif n % 6 == 2:
        print("88" + c * ((n - 14) // 6))
    elif n % 6 == 3:
        print("888" + c * ((n - 21) // 6))
    elif n % 6 == 4:
        print("8888" + c * ((n - 28) // 6))
    else:
        print("88888" + c * ((n - 35) // 6))
    exit()

print("8" * (n // 7))

Solution (Python):
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0])

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

print(ans)

Solution (Python):
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

print(ans)

Solution (Python):
n, m = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

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

dp = [[0 for i in xrange(10)] for j in xrange(n + 1)]

for i in xrange(2, n + 1):
    nl = [0 for k in xrange(10)]
    for dig in a:
        if i - sticks[dig] < 0: continue
        if i - sticks[dig] > 0 and dp[i - sticks[dig]][0] == 0: continue
        cur = [dp[i - sticks[dig]][j] for j in xrange(10)]
        
        cur[10 - dig] += 1
        cur[0] += 1
        
        nl = max(nl, cur)
    
    dp[i] = nl
    



out = []
for i in xrange(1, 10):
    if dp[n][i] == 0: continue
    for j in xrange(dp[n][i]): out.append(str(10 - i))

print ''.join(out)