Buggy python submission (verdict: Runtime Error):
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    steps += 1
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if m > s:
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)


Fixed submission:
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if m > s:
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)

Buggy python submission (verdict: Time Limit Exceeded):
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)


Fixed submission:
n_max = 100000

bs = [(6 ** i, 6) for i in range (1, 10)]
bs.extend([(9 ** i, 9) for i in range (1, 10)])
bs = list(sorted(filter(lambda x: x[0] <= n_max, bs)))
bms = []
s = 5
for b, i in bs:
    s += b * (i - 1)
    bms.append((b, i, s))

#print(bs)
#print(bms, len(bms))

#m = 44852
m = int(input())

stack = [(m, 0, len(bms) - 1)]
#print("search start!")
result = 10000
while stack:
    m, n, bms_i = stack.pop()
    b, i, s = bms[bms_i]
    #print(m, n, bms_i, b, i, s)

    if n > result:
        #print("skip!", m, n, bms_i)
        continue
    if m > s:
        continue
    if bms_i < 0:
        if m <= 6 and m + n < result:
            result = m + n
        #    print('get result!', result)
        continue

    for j in range(i):
        next_m = m - b * j
        if next_m >= 0 and n + j < result:
            stack.append((next_m, n + j, bms_i - 1))

print(result)