Igor has fallen in love with Tanya. Now Igor wants to show his feelings and write a number on the fence opposite to Tanya's house. Igor thinks that the larger the number is, the more chance to win Tanya's heart he has. 

Unfortunately, Igor could only get v liters of paint. He did the math and concluded that digit d requires a_{d} liters of paint. Besides, Igor heard that Tanya doesn't like zeroes. That's why Igor won't use them in his number.

Help Igor find the maximum number he can write on the fence.


-----Input-----

The first line contains a positive integer v (0 ≤ v ≤ 10^6). The second line contains nine positive integers a_1, a_2, ..., a_9 (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Print the maximum number Igor can write on the fence. If he has too little paint for any digit (so, he cannot write anything), print -1.


-----Examples-----
Input
5
5 4 3 2 1 2 3 4 5

Output
55555

Input
2
9 11 1 12 5 8 9 10 6

Output
33

Input
0
1 1 1 1 1 1 1 1 1

Output
-1

Difficulty: interview

Starter code:

Solutions:
#!/usr/local/bin/python3.3 -tt

import sys

def __starting_point():
    def _(f):
        for l in f:
            for i in l.split():
                yield int(i)

    g = _(sys.stdin)

    v = next(g)

    ar = []
    for i in range(9):
        ar.append((next(g), i + 1))

    dominant = min(ar, key=lambda t: (t[0], -t[1]))
    
    digits = v // dominant[0]

    v -= dominant[0] * digits

    ar = [(a - dominant[0], n) for a, n in ar if a > dominant[0] and n > dominant[1]]
    
    ar.sort(key=lambda x: (-x[1], x[0]))

    print(ar, file=sys.stderr)
    
    s = ''

    for a, n in ar:
        if a <= v:
            q = v // a
            v -= q * a
            s += str(n) * q

    s = '%s%s' % (s, str(dominant[1]) * (digits - len(s)))
    
    if s:
        print(s)
    else:
        print(-1)

__starting_point()

import sys
v=int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().split()))

ind=1
vol=A[0]

for i in range(1,10):
    if(A[i-1]<vol):
        vol=A[i-1]
        ind=i
    elif(A[i-1]==vol and i>ind):
        vol=A[i-1]
        ind=i

used=(v//vol)*vol

rest=v-used

x=rest-1
z=0
ans=list(str(ind)*(v//vol))

while(len(ans)!=0 and x!=rest and z<len(ans)):
    x=rest
    for i in range(9,0,-1):
        if(A[i-1]-A[ind-1]<=rest):
            rest-=A[i-1]-A[ind-1]
            ans[z]=str(i)
            z+=1
            break
Ans=""
for item in ans:
    Ans+=item
if(len(Ans)==0):
    print(-1)
else:
    sys.stdout.write(Ans)



v = int(input())
a = list(map(int, input().split()))

i = 0
for j in range(1, len(a)):
  if a[j] <= a[i]:
    i = j

n = v // a[i]
s = a[i] * n
b = []
while s <= v:
  j = len(a) - 1
  while j > i:
    if s + (a[j] - a[i]) <= v:
      break
    j -= 1
  if j == i:
    break
  s += a[j] - a[i]
  b += [j + 1]
  
if s > 0:
  print(''.join(map(str, b + [i + 1] * (n - len(b)))))
else:
  print(-1)

3

def readln(): return tuple(map(int, input().split()))

n, = readln()
a = readln()
m = min(a)
ind = [i for i, _ in enumerate(a) if _ == m][-1]
cnt = [0] * 11
cnt[ind + 1] = n // m
ost = n % m
while cnt[ind + 1] > 0:
    ost += m
    var = [i for i, _ in enumerate(a) if m < _ <= ost and i > ind]
    if var:
        cnt[ind + 1] -= 1
        cnt[var[-1] + 1] += 1
        ost -= a[var[-1]]
    else:
        break
if cnt[ind + 1]:
    for i in range(9, 0, -1):
        print(str(i) * cnt[i], end='')
    print()
else:
    print(-1)


def f(t, k, d):
    j = k - 1
    for i in range(k, 9):
        if d >= t[i]: j = i
    return d - t[j], j + 1

n = int(input())
t = list(map(int, input().split()))
m, k = t[0], 1
for i, x in enumerate(t, 1):
    if x <= m: m, k = x, i
if n < m: print(-1)
else:
    d, j, s = n % m, k + 1, []
    while j != k:
        d, j = f(t, k, d + m)
        s.append(j)
    print(''.join(map(str, s)) + str(k) * (n // m - len(s)))

import sys
v=int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().split()))
ind=1
ind=1
vol=A[0]

for i in range(1,10):
    if(A[i-1]<vol):
        vol=A[i-1]
        ind=i
    elif(A[i-1]==vol and i>ind):
        vol=A[i-1]
        ind=i

used=(v//vol)*vol

rest=v-used

x=rest-1
z=0
ans=list(str(ind)*(v//vol))

while(len(ans)!=0 and x!=rest and z<len(ans)):
    x=rest
    for i in range(9,0,-1):
        if(A[i-1]-A[ind-1]<=rest):
            rest-=A[i-1]-A[ind-1]
            ans[z]=str(i)
            z+=1
            break
Ans=""
for item in ans:
    Ans+=item
if(len(Ans)==0):
    print(-1)
else:
    sys.stdout.write(Ans)



v = int(input())
digits =[int(i) for i in input().split()]

m, ind = digits[0], 0
for i in range(1, 9):
    if digits[i] <= m: m, ind = digits[i], i

number = str(ind + 1) * (v // m)
l = len(number)
if l == 0: print(-1)
else:
    cost = l * m
    for i in range(l):
        for j in reversed(list(range(ind + 1, 9))):
            if v - cost + m >= digits[j]:
                number = number[: i] + str(j + 1) + number[i + 1: ]
                cost = cost - m + digits[j]
                break

    print(number)




v=int(input())
a=list(map(int,input().split()))
i=0
for j in range(1,9):
    if a[j]<=a[i]:
        i=j
if v//a[i]==0:
    print(-1)
else:
    length=v//a[i]
    b=(v//a[i])*a[i]
    ans=[]
    while v>=b:
        j=8
        while j>i:
            if v>=b+a[j]-a[i]:
                break
            j-=1
        if j==i:
            break
        b+=a[j]-a[i]
        ans+=[j+1]
    print(''.join(map(str,ans+[i+1]*(length-len(ans)))))
    


import math

start = int(input())
costs = list(map(int, input().split()))
scosts = [(x+1, costs[x]) for x in range(len(costs))]
scosts.sort(reverse = True)
mincost = scosts[0][1]
minnum = scosts[0][0]
for val, cost in scosts:
    if cost < mincost:
        mincost = cost
        minnum = val
best = [minnum for x in range(start//mincost)]
rem = start - (start//mincost)*mincost
for i in range(len(best)):
    changed = False
    for val, cost in scosts:
        if val > best[i] and (cost-mincost) <= rem:
            rem += mincost
            rem -= cost
            best[i] = val
            changed = True
            break
    if not changed:
        break
if len(best) == 0: print(-1)
else:
    ans = ""
    for val in best:
        ans+=str(val)
    print(ans)

import math

start = int(input())
costs = list(map(int, input().split()))
scosts = [(x+1, costs[x]) for x in range(len(costs))]
scosts.sort(reverse = True)
mincost = scosts[0][1]
minnum = scosts[0][0]
for val, cost in scosts:
    if cost < mincost:
        mincost = cost
        minnum = val
best = [minnum for x in range(start//mincost)]
rem = start - (start//mincost)*mincost
for i in range(len(best)):
    changed = False
    for val, cost in scosts:
        if val > best[i] and (cost-mincost) <= rem:
            rem += mincost
            rem -= cost
            best[i] = val
            changed = True
            break
    if not changed:
        break
if len(best) == 0: print(-1)
else:
    ans = ''.join(map(str,best))
    # for val in best:
    #     ans+=str(val)
    print(ans)

import math

start = int(input())
costs = list(map(int, input().split()))
scosts = [(x+1, costs[x]) for x in range(len(costs))]
scosts.sort(reverse = True)
mincost = scosts[0][1]
minnum = scosts[0][0]
for val, cost in scosts:
    if cost < mincost:
        mincost = cost
        minnum = val
best = [minnum for x in range(start//mincost)]
rem = start - (start//mincost)*mincost
for i in range(len(best)):
    changed = False
    for val, cost in scosts:
        if val > best[i] and (cost-mincost) <= rem:
            rem += mincost
            rem -= cost
            best[i] = val
            changed = True
            break
    if not changed:
        break
if len(best) == 0: print(-1)
else:
    ans = ''.join(map(str,best))
    print(ans)

import sys

TESTING = False

def solve():
    start, = read()
    costs = read()
    scosts = [(x+1, costs[x]) for x in range(len(costs))]
    scosts.sort(reverse = True)
    mincost = scosts[0][1]
    minnum = scosts[0][0]
    for val, cost in scosts:
        if cost < mincost:
            mincost = cost
            minnum = val
    best = [minnum for x in range(start//mincost)]
    rem = start - (start//mincost)*mincost
    for i in range(len(best)):
        changed = False
        for val, cost in scosts:
            if val > best[i] and (cost-mincost) <= rem:
                rem += mincost
                rem -= cost
                best[i] = val
                changed = True
                break
        if not changed:
            break
    if len(best) == 0: return -1
    else:
        ans = ''.join(map(str,best))
        return ans







def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0: return inputs
    if mode == 1: return inputs.split()
    if mode == 2: return list(map(int, inputs.split()))

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

def run():
    if TESTING: sys.stdin  = open("test.txt")
    res = solve()
    write(res)
run()

import sys

TESTING = False

def solve():
    start, = read()
    costs = read()
    scosts = [(x+1, costs[x]) for x in range(len(costs))]
    scosts.sort(reverse = True)
    mincost = scosts[0][1]
    minnum = scosts[0][0]
    for val, cost in scosts:
        if cost < mincost:
            mincost = cost
            minnum = val
    best = [minnum for x in range(start//mincost)]
    rem = start - (start//mincost)*mincost
    for i in range(len(best)):
        changed = False
        for val, cost in scosts:
            if val > best[i] and (cost-mincost) <= rem:
                rem += mincost
                rem -= cost
                best[i] = val
                changed = True
                break
        if not changed:
            break
    if len(best) == 0: return -1
    else:
        ans = ''.join(map(str,best))
        return ans

def read(mode=2):
    inputs = input().strip()
    if mode == 0: return inputs #String
    if mode == 1: return inputs.split() #List of strings
    if mode == 2: return list(map(int, inputs.split())) # List of integers

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

def run():
    if TESTING: sys.stdin  = open("test.txt")
    res = solve()
    write(res)
run()

v = int(input())
a = [int(i) for i in input().split()]
ans = (v//min(a))*[9-a[::-1].index(min(a))]
v %= min(a)
for i in range(len(ans)):
    for j in range(8,-1,-1):
        if j+1 > ans[i] and a[j]-a[ans[i]-1] <= v:
            v -= a[j]-a[ans[i]-1]
            ans[i] = j+1
    if v <= 0:
        break
if ans:
    print("".join([str(i) for i in ans]))
else:
    print(-1)


n=int(input())

S=list(map(int,input().split()))
K=[0]*9
m=min(S)
d=0
di=0
len = n//m
if not len:
    print(-1)
else:
    for i in range(8,-1,-1):
        if S[i]==m:
            d=i+1
            break
    n-=(n//m)*m
    S=list(map(lambda x: x-m, S))
    for i in range (8,-1,-1):
        if S[i]:
            print(str(i+1)*(n//S[i]),end='')
            len -= n//S[i]
            n-= (n//S[i])*S[i]
        else:
            print(str(i+1)*len)
            n=0
            break


x = int(input())
l = [0]+list(map(int, input().split(' ')))
m = 10**9
ind = 0
for i in range(1, 10):
    if l[i] <= m:
        m = l[i]
        ind = i

if m > x:
    print(-1)
    quit()

dig = x // m

k = [ind] * dig
left = x-dig*m
for i in range(dig):
    for j in range(9, 0, -1):
        diff = l[j]-l[k[i]]
        if diff <= left:
            left -= diff
            k[i] = str(j)
            break
    k[i] = str(k[i])

print(''.join(k))


__author__ = "runekri3"

v = int(input())
digit_costs = [10 ** 7] + list(map(int, input().split()))
temp_list = list(enumerate(digit_costs[:]))
temp_list.sort(key=lambda item: item[1], reverse=True)
temp_list.reverse()
digits_by_price = [digit for digit, cost in temp_list]
cheapest_digit = digits_by_price[0]
extra_costs = [digit_cost - digit_costs[cheapest_digit] for digit_cost in digit_costs]
better_digits = [i for i in range(1, 10) if i > cheapest_digit]
better_digits.sort(reverse=True)

max_len = int(v / digit_costs[cheapest_digit])
if max_len > 0:
    current_number = [str(cheapest_digit)] * max_len
    leftover = v % digit_costs[cheapest_digit]
    for index_being_changed in range(max_len):
        for better_digit in better_digits:
            if extra_costs[better_digit] <= leftover:
                leftover -= extra_costs[better_digit]
                current_number[index_being_changed] = str(better_digit)
                break
        else:  # Not enough paint to change digits
            break
else:
    current_number = "-1"
print("".join(current_number))


v = int(input())
A = list(map(int, input().split()))
if v < min(A):
	print(-1)
else:
	basic = 1
	for i in range(9):
		if A[i] <= A[basic - 1]:
			basic = i + 1
	ans = [basic] * (v // A[basic - 1])
	ost = v % A[basic - 1]
	now = 0
	find = True
	while find:
		find = False
		for i in range(8, basic - 1, -1):
			if A[i] <= A[basic - 1] + ost:
				ans[now] = i + 1
				ost = ost + A[basic - 1] - A[i]
				now += 1
				find = True
				break
	print("".join(list(map(str, ans))))



def main():
    v = int(input())
    l = list((w, 9 - d) for d, w in enumerate(map(int, input().split())))
    w, d0 = min(l)
    le = v // w
    if not le:
        print(-1)
        return
    res = [str(10 - d0)] * le
    v -= w * le
    base, start = w, 0
    l = sorted(((10 - d, w - base) for w, d in l if d < d0))
    while l:
        d, w = l.pop()
        delta = v // w
        res[start:start + delta] = [str(d)] * delta
        start += delta
        v -= w * delta
    print(''.join(res))


def __starting_point():
    main()

__starting_point()

v = int(input())
a = list(map(int, input().split()))
m = list(enumerate(a, 1))
k = sorted(m, key=lambda x:(-x[1], x[0]))[-1]
t = v // k[1]
v -= t * k[1]
num = [k[0]] * t
for i in range(t):
    if v + k[1] > min(a):
        num[i] = list(q for q in m if q[1] <= v + k[1])[-1][0]
        v -= a[num[i] - 1] - k[1]
    else:
        break;
print(''.join(map(str, num)) or -1)


n = int(input())
ai = [int(x) for x in input().split()]
mcDigit = 0
for i in range (9):
    if ai[i] <= ai[mcDigit]:
        mcDigit = i

di = [ x-mcDigit for x in ai]
resLen = n // ai[mcDigit]
res = [mcDigit] * resLen
remain = n - resLen * ai[mcDigit]
for i in range(resLen):
    if remain <= 0:
        break
    d = 8
    while d>mcDigit:
        if remain >= (ai[d] - ai[mcDigit]):
            res[i] = d
            remain -= (ai[d] - ai[mcDigit])
            break
        d -= 1
    if d == mcDigit:
        break

out = ""
for i in res:
    out = out + str(i+1)
if resLen == 0:
    print ("-1")
else :
    print (out)

v = int(input())
a = list(map(int, input().split()))

index, val = -1, 10**12
for i in range(len(a)):
    if a[i] <= val:
        val = a[i]
        index = i

m = v // val

ans = [str(index + 1) for x in range(m)]


if not len(set(a)) == 1:
    left = v - m*val
    for i in range(len(ans)):
        potential = left + val
        for j,k in enumerate(reversed(a)):
            if k <= potential:
                left = potential - k
                ans[i] = str(9 - j)
                break

print("".join(ans) if ans else -1)

v = int(input())
a = [-1] + list(map(int, input().split()))
q = [0] * 10
if v < min(a[1:]):
  print(-1)
else:
  top_digit = -1
  for i in range(1, 10):
    if a[i] == min(a[1:]):
      top_digit = i
  q[top_digit] = v // a[top_digit]
  rem = v % a[top_digit]
  for i in range(9, top_digit, -1):
    if a[i] - a[top_digit] <= rem:
      add = min(rem // (a[i] - a[top_digit]), q[top_digit])
      q[i] += add
      q[top_digit] -= add
      rem = rem - add * (a[i] - a[top_digit])
  print("".join([str(i) * q[i] for i in range(9, 0, -1)]))

v = int(input())
a=list(map(int,input().split()))
m,j=a[0],0
for i,x in enumerate(a,1):
    if x<=m: m,j=x,i
x=int(v/m)
if(x==0):
    print(-1)
else:
    while x:
        x-=1
        i=9
        while i:
            i-=1
            if ((v>=a[i])&(int((v-a[i])/m) == x)):
                v-=a[i]
                print(i+1,end='')
                break
        if i+1==j:
            break
    print(x*str(j))