Given a positive integer, write it as the sum of numbers, where each of them is in $kin1,9,81,tin1,2,3,...,64$. How many numbers at least are used? Shortest code win.

Samples:

Input Output Method
1 1 1
2 1 2
64 1 64
65 2 64+1
72 1 72
343 2 342+1
576 1 576
577 2 576+1
5184 1 5184
46656 9 5184+5184+5184+5184+5184+5184+5184+5184+5184
5274 2 5184+90

Jelly, 17 bytes

64R×9;Ɗ⁺ff€¥@ŒṗẈṂ

Try it online!

-1 thanks to Jonathan Allan.

Explanation (you can't test for inputs larger than 58 over TIO):

64R×9;Ɗ⁺ff€¥@ŒṗẈṂ Arguments: x
64R [1..64]
 ×9;Ɗ Multiply by 9, prepend to original list
 ⁺ Do the above once more
 Œṗ Positive integer partitions of x
 ¥@ Call with reversed arguments (x = partitions, y = flattened outer product)
 f€ For each partition in x, keep the elements that are in y
 f Keep the elements of x that have remained intact after the above
 Ẉ Lengths of the remaining partitions
 Ṃ Minimum

JavaScript (ES6), 72 66 57 56 bytes

Saved 1 byte thanks to @nwellnhof

f=n=>n&&1+f(n<5184?n>64&&n%(n<576?9:n>719?81:72):n-5184)

Try it online!

05AB1E (legacy), 30 bytes

5184‰`91SvDy64*›i1sy9*%}}64/îO

Try it online!

This is my first 05AB1E submission, so I am sure that this can be optimized.

Perl 6, 47 bytes

+($_,(*X-(1,9,81 X*^65)).grep(*>=0).min...^0)

Try it online!

A greedy algorithm seems to work.