ll@n,@p,@k,d[k+1]{p};rep(i,n){ll@t,@b;rrep(j,k)d[j+1]>?=t*d[j]+b;}wt(d[k]-1ull>1d18?-1:d[k]);