$K=<>=~$"*$';@_=<>;$\=1e9;$%=$L+$\>>1,$k=$K,map($k-=$-=/ /+($'<$%?$':$%)-$`,@_),$k>0?$L:$\=$%while$\-$L>1;print