Metaprogramming

Time limit1sMemory limit1024 MB

Summary

Find the shortest program of add n, multiply n, and print commands that maps each given distinct input to its required output, or report that none exists.

Level: Medium6 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Problem

Justas often takes part in programming contests. Because he spends so much time solving tasks, he wants to automate the process: he would like a tool that, given a task's tests, finds a program that solves it. Help Justas.

Justas gives you a list of tests, and you must find a program that handles all of them correctly. Each test consists of two integers — the test's input value and the expected result. All input values are distinct.

The programming language Justas uses is very simple. A program has a single variable that holds a non-negative integer of unbounded size. When the program starts, the test's input value is placed in this variable. The program is a list of commands:

add n — add $n$ to the variable ( $0 \le n < 10^9$ ).
multiply n — multiply the variable by $n$ ( $0 \le n < 10^9$ ).
print — output the value of the variable followed by a newline character.

For example, consider this program:

add 5
multiply 8
print

If the input value is $1$ , it prints $48$ ; if the input value is $25$ , it prints $240$ .

Justas does not want his solutions to exceed the time limit, so you must find a program with the fewest commands that correctly handles all of the given tests.

Input

The first line contains an integer $N$ — the number of tests. Each of the next $N$ lines contains two integers $a_i$ and $b_i$ — the input value and the required result of the $i$ -th test. All $a_i$ are distinct.

Output

Print a single integer $K$ — the number of commands in the shortest program that correctly handles every test (the print command is counted too). If no such program exists, print $-1$ .

Constraints

$1 \le N \le 50$
$0 \le a_i, b_i < 10^9$

Examples3

Example 1
Input
```
3
2 12
3 18
5 30
```
Expected output
```
2
```
Example 2
Input
```
1
15 8
```
Expected output
```
3
```
Example 3
Input
```
2
1 3
2 2
```
Expected output
```
-1
```