Chemistry Experiment

There are n kinds of chemical reagents, and all M mg of solution must be distributed among them.

If x mg of solution is added to reagent i, it produces a_i x + b_i mg of a certain gas. The amount x added to each reagent must be a positive integer.

Determine whether the M mg of solution can be distributed among the n reagents so that every reagent produces the same amount of gas. If it is possible, print that common amount of gas. Otherwise, print 0.

The first line contains the number n of reagent kinds. (1 <= n <= 100)

Each of the next n lines contains two integers a_i and b_i, separated by a space. (1 <= a_i <= 100, 1 <= b_i <= 1000)

The last line contains the total amount M of solution. (1 <= M <= 10000)

If the solution can be distributed so that every reagent produces the same amount of gas, print that gas amount on the first line.

If no such distribution exists, print 0.