$a[1<<$_]=<>for@@=0..<>;$_=$a[@d&-@d]+$a[@d&$#d],@d[@d+0]=sort{$a-$b}map{(($-=$a[$k=1<<$_]-$a[$k^=@d]%1e3)+$d[$k])x($k<@d)}@@for@a;print$d[-2]