Tour de France

Time limit1sMemory limit128 MB

Summary

Given front and rear sprocket tooth counts, find the maximum ratio between adjacent attainable drive ratios n/m across all pairs.

Level: Medium5 of 10
Topics: Sorting, Math, Brute force, Number theory
Solved: No attempts yet

Problem

A racing bicycle is driven by a chain that connects two sprockets. The sprockets form two clusters: a front cluster (usually 2 or 3 sprockets) and a rear cluster (usually 5 to 10 sprockets). At any moment the chain links exactly one front sprocket to one rear sprocket.

The drive ratio -- the ratio of the angular velocity of the pedals to that of the wheels -- equals $n:m$ , where $n$ is the number of teeth on the chosen rear sprocket and $m$ is the number of teeth on the chosen front sprocket.

Two drive ratios $d_1 < d_2$ are adjacent when no other attainable drive ratio $d_3$ satisfies $d_1 < d_3 < d_2$ . The spread of a pair $d_1 < d_2$ is their quotient $d_2 / d_1$ .

For a given pair of front and rear clusters, compute the maximum spread over all adjacent pairs of attainable drive ratios.

Input

The input contains several test cases and ends with a line containing a single $0$ .

Each test case consists of:

$f$ : the number of sprockets in the front cluster;
$r$ : the number of sprockets in the rear cluster;
$f$ integers giving the teeth counts of the front sprockets;
$r$ integers giving the teeth counts of the rear sprockets.

No cluster has more than $10$ sprockets, and every sprocket has at least $10$ and at most $100$ teeth.

Output

For each test case, print the maximum spread rounded to two decimal places (rounding halves up), one value per line.

Examples2

Example 1
Input
```
2 4
40 50
12 14 16 19
0
```
Expected output
```
1.19
```
Example 2
Input
```
1 2
10
10 100
0
```
Expected output
```
10.00
```