Chemistry Experiment

Interview

Time limit2sMemory limit128 MB

Summary

Decide whether M mg of solution can be split into positive integer amounts per reagent so every reagent's linear gas formula a_i*x+b_i gives the same value, and output that value or 0.

Level: Medium5 of 10
Topics: Binary search, Math, Brute force
Solved: No attempts yet

Problem

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.

Input

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)

Output

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.

Examples2

Example 1
Input
```
3
3 5
4 3
1 7
27
```
Expected output
```
23
```
Example 2
Input
```
3
3 5
4 3
1 7
26
```
Expected output
```
0
```