($N,@M)=<>;@q=0;while(@q){$q=shift@q;$q>>$_&1or$p[$Q=$q|1<<$_]//=($m[$Q]=$m[$q]+$M[$_],9e9*push@q,$Q),$p[$Q]-=$-=$p[$Q]-$p[$q]-($-=$M[$_]-$m[$q]%1e3)for 0..15}print$p[-1]