#!ruby -nrprime
d=*[-1]*n=$_.to_i,0
Prime.each(499){|p|p.upto(n){|i|t=d[i]+1;t>0&&d[i-=p]<t&&d[i]=t}}
p d[0]