N=eval *$<
q=[[1,0]]
q.map{|j,v|j>N||$*[j]||=q<<[j+b=("%b"%j).sum%48,v+=1]<<[j-b,v]&&v}
p $*[N]||-1