Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
The total cost used must be equal to target.
Integer does not have digits 0.

Since the answer may be too large, return it as string.
If there is no way to paint any integer given the condition, return "0".
 
Example 1:
Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation:  The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "977", but "7772" is the largest number.
Digit    cost
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

Example 2:
Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.

Example 3:
Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It's not possible to paint any integer with total cost equal to target.

Example 4:
Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"

 
Constraints:

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

Difficulty: interview

Starter code:

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        

Solutions:
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-target]*target
        for t in range(1, target+1):
            dp[t] = max([dp[t-i] for i in cost if i<=t]+[dp[t]]) + 1
        if dp[-1]<=0: return '0'
        res = ''
        for i in range(8, -1, -1):
            while target>=cost[i] and dp[target-cost[i]]==dp[target]-1:
                res += str(i+1)
                target -= cost[i]
        return res

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        @lru_cache(None)
        def dfs(c):
            #if c==0: print(c,cur)
            if c == 0: return 0
            ans = -float('inf')
            for i in range(9):
                if cost[i] <= c:
                    ans = max(ans,10 * dfs(c-cost[i])+i+1)
            return ans
        res = dfs(target)
        return str(res) if res> 0 else '0' 
'''
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        from functools import lru_cache
        @lru_cache(None)
        def dfs(target):
            if target == 0: return 0
            res = -float(\"inf\")
            for i in range(len(cost)):
                if cost[i] <= target:
                    res = max(res, 10*dfs(target - cost[i])+i+1)
            return res
        res = dfs(target)
        return str(res) if res > 0 else \"0\"
'''

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * (target + 5000)
        for t in range(1, target + 1):
            dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
        return str(max(dp[t], 0))

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
    
        def memo(f):
            dic = {}
            def f_alt(*args):
                if args not in dic:
                    dic[args] = f(*args)
                return dic[args]
            return f_alt

        key = lambda s: (len(s),s)
        
        cands = {}
        for i,c in enumerate(cost):
            cands[c]=i+1
        
        @memo
        def f(tar):
            if tar == 0:
                return 0
            if tar>0:
                ans = 0
                for c in cands:
                    if f(tar-c) != None:
                        ans = max(ans, 10*f(tar-c) + cands[c])
                return ans or None
        
        return str(f(target) or 0)


'''
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        @lru_cache
        def dfs(c, cur):
            #if c==0: print(c,cur)
            if c < 0: return 0
            if c == 0: return cur 
            ans = 0
            for i in range(9):
                ans = max(ans,dfs(c-cost[i], 10*cur+i+1))
            return ans
        return str(dfs(target, 0))
'''
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        '''
        from functools import lru_cache
        @lru_cache(None)
        def dfs(target,count):
            if target == 0:
                return 0
            
            res = -float(\"inf\")
            
            for i in range(len(cost)):
                if cost[i] <= target:
                    res = max(res, 10*dfs(target - cost[i], count+1)+i+1)
            
            
            return res
        
        res = dfs(target,0)
        
        return str(res) if res > 0 else \"0\"
        '''
        dp = [0] + [-1] * (target + 5000)
        for t in range(1, target + 1):
            dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
        return str(max(dp[t], 0))

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * (target + 5000)
        for t in range(1, target + 1):
            p = iter(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
            dp[t] = max(p)
        return str(max(dp[t], 0))


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [float('-inf')] * (target + 1)
        dp[0] = 0
        for i in range(1, 10):
            for j in range(1, target + 1):
                c = cost[9 - i]
                if c <= j:
                    dp[j] = max(dp[j - c] * 10 + (10 - i), dp[j])
                    
        return str(dp[target]) if str(dp[target]) != '-inf' else '0'

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
          dp = [0] + [-1] * (target+ 5000)
          for t in range(1, target + 1):
            dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
            #print(dp)
          return str(max(dp[t], 0))


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0]
        for i in range(1,target+1):
            result = 0
            for j,c in enumerate(cost):
                if i<c:
                    continue
                if dp[i-c] == 0 and i!=c:
                    continue
                result = max(result,10*dp[i-c]+j+1)
            dp.append(result)
        return str(dp[-1])

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        '''dp = [0]
        for i in range(1,target+1):
            result = 0
            for j,c in enumerate(cost):
                if i<c:
                    continue
                if dp[i-c] == 0 and i!=c:
                    continue
                result = max(result,10*dp[i-c]+j+1)
            dp.append(result)
        return str(dp[-1])'''
        cache = {}
        def helper(remaining):
            if remaining == 0:
                return ''
            if remaining in cache:
                return cache[remaining]
            maximum = '0'
            for i in range(len(cost)):
                if cost[i] > remaining:
                    continue
                result = helper(remaining - cost[i])
                if result == '0':
                    continue
                maximum = larger(maximum, str(i+1) + result)
            cache[remaining] = maximum
            return maximum

        def larger(a, b):
            if len(a) > len(b):
                return a
            if len(a) < len(b):
                return b
            return max(a, b)

        return helper(target)

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [float('-inf')] * target
        for i in range(9, 0, -1):
            for j in range(1, target+1):
                if j >= cost[i - 1]:
                    dp[j] = max(dp[j], (dp[j-cost[i - 1]] * 10) + i)
        return str(dp[target]) if dp[target] > 0 else '0'



class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] * (target+1)
        
        for t in range(1, target+1):
            for d, c in zip(range(1, len(cost)+1), cost):
                if t==c:
                    dp[t] = max(dp[t], d)
                if c < t and dp[t-c] != 0:
                    dp[t] = max(dp[t], dp[t-c] * 10 + d)
        # print(dp)
        return str(dp[target])

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * (target)
        for t in range(1, target + 1):
            for i, c in enumerate(cost):
                if t - c >= 0:
                    dp[t] = max(dp[t], dp[t - c] * 10 + i + 1)
        return str(max(dp[target], 0))


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0]
        for i in range(1,target+1):
            best = 0
            for j, c in enumerate(cost):
                if i - c < 0:
                    continue
                if dp[i-c] == 0 and i != c:
                    continue
                best = max(best, 10*dp[i-c] + j + 1)
            dp.append(best)
        return str(dp[-1])
        
        
        
        
        
        
        
        
        
        
        
        
        '''
        pairs = [(c,-i-1) for i,c in enumerate(cost)]
        #pairs.sort()
        out = 0
        def dfs(target, painted) -> bool:
            nonlocal out
            if target == 0:
                out = max(out,int(painted))
                return
            if target < 0:
                return
            for i in range(9):
                dfs(target - pairs[i][0], painted + str(-pairs[i][1]))
        dfs(target,\"\")
        return str(out)
        '''          

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        #def largestNumber(self, cost, target):
            
        dp = [0] + [-1]*(target)
        for i in range(1,target+1):
            for j,c in enumerate(cost):
                if c<=i:
                    dp[i] = max(dp[i],dp[i-c]*10 + j + 1)
                
        
        return str(max(dp[target],0))
            


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * (5000+ target)
        for i in range(1, target+1):
            for j, c in enumerate(cost):
                dp[i] = max(dp[i], 10 * dp[i-c] + j + 1)
        return str(max(dp[target], 0))
    '''  
    def largestNumber(self, cost, target):
        dp = [0] + [-1] * (target + 5000)
        for t in xrange(1, target + 1):
            dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
        return str(max(dp[t], 0))
    '''

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        self.min_cost = min(cost)
        self.cost = cost
        self.mem = dict()
        rv = self.dfs(target)
        if rv is None:
            return '0'
        return rv
        
    def dfs(self, target):
        if target == 0:
            return ''
        elif target < self.min_cost:
            return None
        
        key = (target)
        if key in self.mem:
            return self.mem[key]
        
        res = ''
        for i, c in enumerate(self.cost):
            rv = self.dfs(target - c)
            if rv != None:
                res = self.get_max(res, str(i+1) + rv)

        if res == '':
            res = None
        self.mem[key] = res
        return res
            
            
            
    def get_max(self, s1, s2):
        if len(s1) != len(s2):
            if len(s1) > len(s2):
                return s1
            return s2
        if s1 > s2:
            return s1
        return s2

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-float('inf')] * (5000+ target)
        for i in range(1, target+1):
            for j, c in enumerate(cost):
                dp[i] = max(dp[i], 10 * dp[i-c] + j + 1)
        return str(max(dp[target], 0))
    '''  
    def largestNumber(self, cost, target):
        dp = [0] + [-1] * (target + 5000)
        for t in xrange(1, target + 1):
            dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
        return str(max(dp[t], 0))
    '''

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * (target)
        for t in range(1, target + 1):
            for i, c in enumerate(cost):
                if t - c >= 0:
                    dp[t] = max(dp[t], dp[t - c] * 10 + i + 1)
        return str(max(dp[target], 0))

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        #since cost limit is 5000, we can add 5000
        #to dp size to avoid checking c < target
        dp = [0] + [-1] * (target + 5000)
        for t in range(1, target + 1):
            for i, c in enumerate(cost):
                #the new digit is i + 1, the previous digit dp[t - 1] move 1 step to left
                dp[t] = max(dp[t], dp[t - c] * 10 + (i + 1))
        #since we set dp initial value to be -1, question require 0 if not found.
        return str(max(dp[target], 0))


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * (target + 1)
        for t in range(1, target + 1):
            dp[t] = max(dp[max(t - c, -1)] * 10 + i + 1 for i, c in enumerate(cost))
        return str(max(dp[t], 0))

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * target
        for t in range(1, target + 1):
            for i, c in enumerate(cost):
                if c <= t:
                    dp[t] = max(dp[t], dp[t - c] * 10 + (i + 1))
        return str(max(dp[-1], 0))



from typing import List
import numpy
import functools

class Solution:

  def largestNumber(self, cost: List[int], target: int) -> str:

    cache = {}
    def solve(remaining):
      if not remaining:
        return ''
      if remaining in cache:
        return cache[remaining]

      maxium = '0'
      for i in range(len(cost)):
        if cost[i] > remaining:
          continue
        result = solve(remaining - cost[i])
        if result == '0':
          continue

        maxium = larger(maxium, str(i+1) + result)
        pass
      cache[remaining] = maxium
      return maxium
      pass

    def larger(a, b):
      if len(a) > len(b):
        return a

      if len(a) < len(b):
        return b

      return max(a, b)

    return solve(target)

from functools import lru_cache

class Solution:
    # def largestNumber(self, cost: List[int], target: int) -> str:
#         def compare(a, b):
#             if len(a) == 0:
#                 return b
#             if sum(a) > sum(b):
#                 return a
#             elif sum(b) > sum(a):
#                 return b
#             else:
#                 j = -1
#                 while j >= -len(a) and a[j] == b[j]:
#                     j -= 1
#                 if j < -len(a):
#                     return a
#                 if a[j] >= b[j]:
#                     return a
#                 else:
#                     return b
                
#         @lru_cache(None)
#         def dfs(idx, tgt):
#             if idx == 0:
#                 if tgt != 0:
#                     return []
#             if tgt == 0:
#                 return [0, 0, 0, 0, 0, 0, 0, 0, 0]
#             out = []
#             for i in range(tgt // cost[idx] + 1):
#                 nxt = dfs(idx - 1, tgt - i * cost[idx])
#                 # print(nxt, i)
#                 if len(nxt) != 0:
#                     new = [x for x in nxt]
#                     new[idx] += i
#                     out = compare(out, new)
#             return out
        
#         ans = '' 
#         r = dfs(8, target)
#         for i, x in enumerate(r):
#             ans += str(i + 1) * x
#         return ans

        def largestNumber(self, cost, target):
            dp = [0] + [-1] * (target + 5000)
            for t in range(1, target + 1):
                dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
            return str(max(dp[t], 0))

def dp(costs, target, mem):
    if target == 0:
        return ''
    elif target in mem:
        return mem[target]
    
    res = ''
    for i in range(len(costs)):
        if target - costs[i] >= 0:
            current = dp(costs, target - costs[i], mem)
            
            if current is not None:
                res = max([res, str(i+1) + current], key=lambda x: (len(x), x))
        
    mem[target] = res if res != '' else None
    return res if res != '' else None

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        result = dp(cost, target, {})
        
        return result if result != '' and result is not None else '0'

class Solution:
    def largestNumber(self, cost, target):
        dp = [0] + [-1] * (target + 5000)
        for t in range(1, target + 1):
            dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
        return str(max(dp[t], 0))

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-1] * (target + 5000)
        for t in range(1, target + 1):
            p = []
            for i, c in enumerate(cost):
                p.append(dp[t - c] * 10 + i + 1)
                dp[t] = max(p)
        return str(max(dp[t], 0))


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        '''dp = [0]
        for i in range(1,target+1):
            result = 0
            for j,c in enumerate(cost):
                if i<c:
                    continue
                if dp[i-c] == 0 and i!=c:
                    continue
                result = max(result,10*dp[i-c]+j+1)
            dp.append(result)
        return str(dp[-1])'''
        cache = {}
        def helper(remaining):
            if remaining == 0:
                return ''
            if cache.get(remaining) is not None:
                return cache[remaining]
            maximum = '0'
            for i in range(len(cost)):
                if cost[i] > remaining:
                    continue
                result = helper(remaining - cost[i])
                if result == '0':
                    continue
                maximum = larger(maximum, str(i+1) + result)
            cache[remaining] = maximum
            return maximum

        def larger(a, b):
            if len(a) > len(b):
                return a
            if len(a) < len(b):
                return b
            return max(a, b)

        return helper(target)

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        cache = {}
        def helper(remaining):
            if remaining == 0:
                return ''
            if remaining in cache:
                return cache[remaining]
            maximum = '0'
            for i in range(len(cost)):
                if cost[i] > remaining:
                    continue
                result = helper(remaining - cost[i])
                if result == '0':
                    continue
                maximum = larger(maximum, str(i+1) + result)
            cache[remaining] = maximum
            return maximum

        def larger(a, b):
            if len(a) > len(b):
                return a
            if len(a) < len(b):
                return b
            return max(a, b)

        return helper(target)

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        Memo = {}
        Min = min(cost)
        Memo[0] = [0,0,0,0,0,0,0,0,0,0]
        def dfs(remain):
            if remain in Memo:
                return Memo[remain]
            if remain < Min:
                Memo[remain] = [0,0,0,0,0,0,0,0,0,-10000000]
                return [0,0,0,0,0,0,0,0,0,-10000000]
            Max = [0,0,0,0,0,0,0,0,0,-10000000]
            flag = False
            for i,c in enumerate(cost):
                tmp = dfs(remain-c)
                if tmp[-1] != -10000000:
                    flag = True
                    newtmp = tmp[:i]+[tmp[i]+1]+tmp[i+1:-1]+[tmp[-1]+1]
                    for j in range(9,-1,-1):
                        if newtmp[j] > Max[j]:
                            Max = newtmp
                            break
                        elif newtmp[j] == Max[j]:
                            continue
                        else:
                            break
            Memo[remain] = Max
            return Max
        r = dfs(target)
        if r[-1] == -10000000:
            return '0'
        else:
            rs = ''
            for k in range(8,-1,-1):
                rs+=str(k+1)*r[k]
        return rs
                    


# 1449. From Largest Integer With Digits That Add up to Target

def prune (costs):
    ans = []
    for ind, elem in enumerate (costs):
        if any (costs[i] + costs[j] == elem for i in range (ind) for j in range (ind)):
            pass
        else:
            ans.append (elem)
    return ans

def find_longest_combos (costs, start, prefix, left, max_yets):
    if start == len (costs):
        if left == 0 and len (prefix) >= max_yets[0]:
            max_yets[0] = len (prefix)
            yield prefix[:]
    else:
        # judge if possible to find as long
        theoretical_max_length = len (prefix) + left // costs[start]
        if theoretical_max_length < max_yets[0]:
            return
        if costs[start] <= left:
            prefix.append (costs[start])
            yield from find_longest_combos (costs, start, prefix, left - costs[start], max_yets)
            prefix.pop ()
        if True:
            yield from find_longest_combos (costs, start + 1, prefix, left, max_yets)

def rlencode (arr):
    ans = []
    for elem in arr:
        if ans and ans[-1][0] == elem:
            ans[-1] = (ans[-1][0], ans[-1][1]+1)
        else:
            ans.append ((elem, 1))
    return ans

def encode (digit_choices, combo):
    return sorted([
        (digit_choices[elem], freq)
        for (elem, freq) in combo
    ], reverse=True)

def write (rle):
    ans = []
    for (elem, freq) in rle:
        for _ in range (freq):
            ans.append (elem)
    return ''.join (map (str, ans))

def gcd (a, b):
    a, b = min (a, b), max (a, b)
    while a > 0:
        a, b = b%a, a
    return b

def gcdall (arr):
    ans = arr[0]
    for elem in arr:
        ans = gcd (ans, elem)
    return ans

def obviously_unsatisfactory (cost, target):
    if min (cost) > target:
        return True
    if target % gcdall (cost) != 0:
        return True
    return False

def largest_num (cost, target):
    if obviously_unsatisfactory (cost, target):
        return '0'
    costs = sorted (list (set (cost)))
    costs = prune (costs)
    combinations = list (find_longest_combos (costs, 0, [], target, [0]))
    if not combinations:
        return '0'
    max_length = max (map (len, combinations))
    combinations = (c for c in combinations if len (c) == max_length)
    digit_choices = {}
    for (i, c) in enumerate (cost):
        digit_choices[c] = i+1
    combinations = map (rlencode, combinations)
    combinations = (encode (digit_choices, combo) for combo in combinations)
    return write (max (combinations))

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        return largest_num(cost, target)

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        
        @lru_cache(None)
        def rec(rem):
            if rem <= 0:
                return 0 if rem == 0 else -math.inf
            
            ans = -math.inf
            for c in cost:
                ans = max(ans, rec(rem - c) + 1)
            return ans
        
        ln = rec(target)
        if ln <= 0:
            return '0'
        
        def path(rem, now):
            # print(rem, now)
            if rem <= 0:
                return now if rem == 0 else ''
            for i, c in enumerate(reversed(cost)):
                if rec(rem - c) + 1 == rec(rem):
                    return path(rem - c, now + str(9 - i))
            return ''
            
        ans = path(target, '')
        print(ans)
        return ans


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        cost_to_digit = {val: str(index+1) for index, val in enumerate(cost)}
        cost = sorted(cost_to_digit.keys())
        @lru_cache(None)
        def helper(target: int) -> str:
            if target < cost[0]:
                return None
            max_number = None if target not in cost_to_digit else cost_to_digit[target]
            for c in cost:
                if c > target:
                    break
                curr_number = helper(target-c)
                if curr_number is None:
                    continue
                curr_number = ''.join(sorted(cost_to_digit[c]+curr_number, reverse=True))
                max_number = curr_number if max_number is None or len(curr_number) > len(max_number) or (len(curr_number) == len(max_number) and curr_number > max_number) else max_number
            #print(target, max_number)
            return max_number
        
        ans = helper(target)
        return ans if ans else '0'

from functools import lru_cache

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        
        ss = set()
        for i, c in enumerate(reversed(cost)):
            if c not in ss:     ss.add(c)
            else:               cost[~i] = float('inf')
        
        cost = list((cost[i], str(i+1)) for i in range(9) if cost[i] != float('inf'))
        
        dp = [[] for _ in range(target+1)]
        for i in range(1, target+1):
            for c, d in cost:
                if i - c == 0 or i - c > 0 and len(dp[i-c]) :
                    tmp = sorted(dp[i-c] + [d], reverse=1)
                    if len(dp[i-c]) + 1 > len(dp[i]):
                        dp[i] = tmp
                    elif len(dp[i-c]) + 1 == len(dp[i]):
                        if tmp > dp[i]:
                            dp[i] = tmp
        return ''.join(dp[-1]) if dp[-1] else '0'

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [0] + [-float('inf')] * (5000+ target)
        for i in range(1, target+1):
            for j, c in enumerate(cost):
                dp[i] = max(dp[i], 10 * dp[i-c] + j + 1)
        print(dp[:target+1])        
        return str(max(dp[target], 0))
    '''  
    def largestNumber(self, cost, target):
        dp = [0] + [-1] * (target + 5000)
        for t in xrange(1, target + 1):
            dp[t] = max(dp[t - c] * 10 + i + 1 for i, c in enumerate(cost))
        return str(max(dp[t], 0))
    '''

from functools import lru_cache

class Solution:
  @lru_cache(None)
  def recursive(self, k):
    if k == 0:
      return ''
    ans = []
    for x in self.d:
      if x <= k:
        r = self.recursive(k - x)
        if r != '0':
          ans.append(self.d[x] + r)
    return str(max(map(int, ans))) if ans else '0'
  def largestNumber(self, cost: List[int], target: int) -> str:
    # self.d: cost -> digit, same cost always prefer larger digit
    self.d = {}
    for i, x in enumerate(cost):
      self.d[x] = str(i + 1)
    self.recursive.cache_clear()
    return self.recursive(target)

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
       
        for i in range(len(cost)):
            for j in range(len(cost)-1, i, -1):
                if cost[j] and not cost[i]%cost[j]:
                    cost[i] = 0
                    break
        costMap = {e: k+1 for k,e in enumerate(cost) if e}
        print((costMap, cost))
        def getMaxList(s1, s2):
            if s2 == None: return ''
            return ''.join(sorted(s1+s2, reverse = True))
              
        def dfs(c):
           
            if c in dp: return dp[c]
            if c == 0: return ''
            elif c < 0: return None
            # print(c)
           
            strs = [getMaxList(str(i), dfs(c-cost[i-1])) for i in range(1,10) if cost[i-1] in costMap]
            if not any(strs): 
                dp[c] = None
                return None
            l = max(list(map(len, strs)))
            newStr = sorted(strs)
            for i in range(len(strs)-1, -1, -1):
                if len(newStr[i]) == l:
                    dp[c] = newStr[i]
                    return dp[c]
        dp = {}
        res = dfs(target)
        return res if res else '0'


from functools import lru_cache

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        
        ss = set()
        for i, c in enumerate(reversed(cost)):
            if c not in ss:     ss.add(c)
            else:               cost[~i] = float('inf')
        
        cost = list((cost[i], str(i+1)) for i in range(9) if cost[i] != float('inf'))
        
        dp = [[] for _ in range(target+1)]
        for i in range(1, target+1):
            for c, d in cost:
                if i - c == 0 or i - c > 0 and len(dp[i-c]) :
                    if len(dp[i-c]) + 1 > len(dp[i]):
                        dp[i] = sorted(dp[i-c] + [d], reverse=1)
                    elif len(dp[i-c]) + 1 == len(dp[i]):
                        tmp = sorted(dp[i-c] + [d], reverse=1)
                        if tmp > dp[i]:
                            dp[i] = tmp
                            
        return ''.join(dp[-1]) if dp[-1] else '0'

def cmp(s, t):
    if len(s) != len(t):
        return len(s) < len(t)
    for i in range(len(s)):
        if s[i] != t[i]:
            return s[i] < t[i]
    return False

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        best = {}
        for i in range(len(cost)-1, -1, -1):
            digit = i+1
            if cost[i] not in best:
                best[cost[i]] = digit
                
        keys = sorted(list(best.keys()), key=lambda x:best[x], reverse=True)
        
        @lru_cache(None)
        def f(t, idx):
            if t == 0:
                return ''
            if t < 0 or idx == len(keys):
                return '0'
            k = keys[idx]
            b = '0'
            best_ct = 0
            for ct in range(t // k, -1, -1):
                r = f(t - k * ct, idx+1)
                if r != '0':
                    if b == '0' or ct + len(r) > best_ct + len(b):
                        b = r
                        best_ct = ct
            return str(best[k]) * best_ct + b
        
        return f(target, 0)


def cmp(s, t):
    if len(s) != len(t):
        return len(s) < len(t)
    for i in range(len(s)):
        if s[i] != t[i]:
            return s[i] < t[i]
    return False

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        best = {}
        for i in range(len(cost)-1, -1, -1):
            digit = i+1
            if cost[i] not in best:
                best[cost[i]] = digit
                
        keys = sorted(list(best.keys()), key=lambda x:best[x], reverse=True)
        
        @lru_cache(None)
        def f(t, idx):
            if t == 0:
                return ''
            if t < 0 or idx == len(keys):
                return '0'
            k = keys[idx]
            b = '0'
            for ct in range(t // k, -1, -1):
                r = f(t - k * ct, idx+1)
                if r != '0':
                    cur = str(best[k]) * ct + r
                    if b == '0' or cmp(b, cur):
                        b = cur
            return b
        
        return f(target, 0)


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        d = {i:-1 for i in cost}
        for i in range(1,len(cost)+1):
            d[cost[i-1]] = max(d[cost[i-1]], i)
        dp = ['-1']*(target+1)
        cost = list(set(cost))
        cost.sort()
        for i in d:
            try:
                dp[i] = str(d[i])
            except:
                pass
        # print(d)
        # print(cost)
        for i in range(1,target+1):
            for j in cost:
                if i - j > 0:
                    if dp[i-j] != '-1':
                        dp[i] = str(max( int(dp[i-j]+str(d[j])) , int(dp[i])))
                    else:
                        try:
                            dp[i] = str(max( int(dp[i]), d[i]))
                        except:
                            pass
                else:
                    break
        if dp[target] == '-1':
            return '0'
        return dp[target]


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        t = target
        dp = [ ['0'] for _ in range(t + 1)] 
        dp[0] = ['']
        for i in range(1, t + 1):
            for j in range(9):
                l1 = len(dp[i]) 
                l1 = 0 if dp[i] == ['0'] else l1
                l2 = len(dp[i - cost[j]]) + 1 if i>=cost[j] else 0
                c = dp[i - cost[j]] if i>=cost[j] else ['0']
                # print(l1,l2)
                if l1 <= l2:
                    dp[i] = c + [str(j + 1)] if c != ['0'] else ['0']
                # if i == t:
                #     print(dp[i], c, l1, l2)
               
            # print(dp[0:][j])
        # print(dp)
        ans = ''.join(sorted(dp[t])[::-1])
        return ans

def cmp(a, b):
    ad, bd = {}, {}
    for i in range(0, len(a), 2):
        ad[a[i]] = a[i+1]
    for i in range(0, len(b), 2):
        bd[b[i]] = b[i+1]
    sad = sum(ad.values())
    sbd = sum(bd.values())
    if sad != sbd:
        return sad < sbd
    al = sorted(list(ad.keys()), reverse=True)
    bl = sorted(list(bd.keys()), reverse=True)
    for i in range(1+min(len(al), len(bl))):
        if al[i] == bl[i]:
            c = al[i]
            if ad[c] != bd[c]:
                return ad[c] < bd[c]
        else:
            return al[i] < bl[i]
    return False
        
    

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        best = {}
        for i in range(len(cost)-1, -1, -1):
            digit = i+1
            if cost[i] not in best:
                best[cost[i]] = digit
                
        x = sorted(best.keys())
        y = sorted(list(best.values()), reverse=True)
        # print(x, y)
        @lru_cache(None)
        def best_path(t, idx):
            if t == 0:
                return tuple()
            if idx == len(x):
                return None
            ret = None
            bi = -1
            for i in range(t // x[idx], -1, -1):
                y = best_path(t - i * x[idx], idx+1)
                if y is not None:
                    if i > 0:
                        y = (best[x[idx]], i) + y
                    if bi == -1 or cmp(ret, y):
                        ret = y
                        bi = i
            # if bi >= 1:
            #     ret = (best[x[idx]], bi) + ret
            # if t == target and idx == 0:
            #     print(ret)
            # if t == target:
            #     print(t, idx, ret)
            return ret
        
        r = best_path(target, 0)
        # print(r)
        if r is None:
            return '0'
        unpacked = {}
        for i in range(0, len(r), 2):
            unpacked[r[i]] = r[i+1]
        s = ''
        # print(y)
        # print(unpacked)
        for digit in y:
            if digit in unpacked:
                s += str(digit) * unpacked[digit]
        return s
        


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        d = {i:-1 for i in cost}
        for i in range(1,len(cost)+1):
            d[cost[i-1]] = max(d[cost[i-1]], i)
        # print(d)
        dp = ['-1']*(target+1)
        cost = list(set(cost))
        cost.sort()
        for i in d:
            try:
                dp[i] = str(d[i])
            except:
                pass
        # print(d)
        # print(cost)
        # print(dp)
        for i in range(1,target+1):
            for j in cost:
                if i - j > 0:
                    # print(int(dp[i-j]+str(d[j])),dp[i], i,j)
                    # print(dp,i,j)
                    if dp[i-j] != '-1':
                        dp[i] = str(max( int(dp[i-j]+str(d[j])) , int(dp[i])))
                    else:
                        try:
                            dp[i] = str(max( int(dp[i]), d[i]))
                        except:
                            pass
                else:
                    break
            # print(dp,i)
        # print(dp)
        if dp[target] == '-1':
            return '0'
        return dp[target]


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        
        @lru_cache(None)
        def rec(rem):
            if rem <= 0:
                return 0 if rem == 0 else -math.inf
            
            ans = -math.inf
            for c in cost:
                ans = max(ans, rec(rem - c) + 1)
            return ans
        
        ln = rec(target)
        if ln <= 0:
            return '0'
        
        def path(rem, now):
            if rem <= 0:
                return now if rem == 0 else ''
            for i, c in enumerate(reversed(cost)):
                if rec(rem - c) + 1 == rec(rem):
                    return path(rem - c, now + str(9 - i))
            return ''
            
        return path(target, '')


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        
        
        # (n) -number, (hp) -health points   <-- both negative for 
        q = [(0, -target)] 
        
        # visited[hp] = largest_number achieved with hp remaining
        visited = {}
        
        # cost of each number
        costs = dict(zip(range(1,10), cost))
        
        # filter costs to remove:
        # i.  any lower number that costs >= a higher number
        # ii. where the lower number's cost is an integer multiple of the higher number
        #     this is important because we need a diverse set of costs to hit target exactly
        for i,a in enumerate(cost,1):
            for b in cost[i:]:
                if (b <= a) and not (a%b):
                    del costs[i]
                    break
        
        while q:
            
            n, hp = heapq.heappop(q)
            n = -n
            hp = -hp
            
            if hp < 0:
                continue
            
            if visited.get(hp, -1) >= n:
                continue
            visited[hp] = n
            
            for c in costs:
                if costs[c] <= hp:
                    heapq.heappush(q, (-(n*10+c), -(hp-costs[c])))
        
        return str(visited.get(0,0))

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        return self.helper(cost, target, {})
        
    def helper(self, cost, target, visited):
        if target == 0:
            return ''
        if target in visited:
            return visited[target]
        ans = '0'
        for i in range(1, 10):
            if target >= cost[i - 1]:
                prev = self.helper(cost, target - cost[i - 1], visited)
                if prev != '0':
                    curr = str(i) + prev
                    if len(curr) >= len(ans) and int(curr) > int(ans):
                        ans = curr
        visited[target] = ans
        return ans

from functools import lru_cache


class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        
        @lru_cache(None)
        def dp(index, remain):
            if remain == 0:
                return ''
            
            elif remain < 0 or index > len(cost):
                return '0'
            
            
            take = str(index) + dp(1, remain - cost[index-1])
            skip = dp(index + 1, remain)
            
            return get_bigger(take, skip)
        
        
        def get_bigger(a, b):
            if '0' in a:
                return b
            
            elif '0' in b:
                return a
            
            elif int(a) > int(b):
                return a
            
            else:
                return b
        
        ans = dp(1, target)
        
        return ans if '0' not in ans else '0'