Number

Time limit2sMemory limit1024 MB

Summary

Given ranges [a,b] and [c,d], find the smallest integer greater than ac that is not a product u*v with u in [a,b] and v in [c,d].

Level: Hard8 of 10
Topics: Math, Number theory, Binary search, Greedy
Solved: No attempts yet

Problem

Given natural numbers $a$ , $b$ , $c$ , and $d$ , find the smallest natural number $n$ greater than $ac$ that cannot be written as the product of two natural numbers $u$ and $v$ with $a \le u \le b$ and $c \le v \le d$ .

Input

The input file contains a single line with the natural numbers $a$ , $b$ , $c$ , and $d$ ( $1 \le a \le b \le 10^6$ , $1 \le c \le d \le 10^6$ ).

Output

Print the number $n$ .

Examples2

Example 1
Input
```
1 2 1 2
```
Expected output
```
3
```
Example 2
Input
```
1 2 3 5
```
Expected output
```
7
```