Bob is travelling the world. During his travel he spends his money very carefully because his budget is short.

While travelling he has reached to a place where he need to cross n stations to go ahead otherwise he will get killed.

At each stations there in a number A and a mathematical operation op . If bob have x rupees with him before reaching on a particular station then after he reaches on the station his left money will be x op A. If at any station his money will become zero or less then he can not go to next station. Now he wonder how much money he should have saved in order to cross all the stations ?

Input
First line contains an integer n ,the number of stations.
Next n line contains a single integer op(i),type of operation to be performed on station number i.
Next n line contains a single integer A(i),the number present on station number i.

Definition of op(i) : if x = money before reaching to station i and left = money after reaching to station i,
then
op(i) = 0 means addition and take remainder by 10^12 + 7 (left = (x+A)%10^12 + 7)
op(i) = 1 means subtraction (left = x-A)
op(i) = 2 means multiplication and then take remainder by 1000000007. (left =( x*A ) mod 1000000007)
op(i) = 3 means division. (left = x/A ){Integer division operation}

Output

Output a single line containing the minimum positive number Bob needs before going to the first station in order to cross all the stations.
If it is not possible to cross all the stations print -1


Constraints
1 <= n<= 10^6 0 <= op(i) <=3
1 <= A(i) <= 10^6

Note :- Bob can not have more than 10^15 rs. before going to first station.