Traveling Monk

Interview

Time limit2sMemory limit1024 MB

Summary

Given the monk's ascent and descent segments on the same path, find the earliest time both trips put him at the same elevation.

Level: Medium5 of 10
Topics: Binary search, Simulation
Solved: No attempts yet

Problem

This puzzle was popularized by Martin Gardner in his book "My Best Mathematical and Logic Puzzles," but it first appeared in the monograph "On Problem-Solving" by the Gestalt psychologist Karl Dunker.

One morning, exactly at sunrise, a Buddhist monk began to climb a tall mountain. The narrow path, no more than a foot or two wide, spiraled around the mountain to a glittering temple at the summit.

The monk ascended the path at varying rates of speed, stopping many times along the way to rest and eat the dried fruit he carried with him. He reached the temple shortly before sunset. After several days of fasting and meditation he began his journey back along the same path, starting at sunrise and again walking at variable speeds with many pauses along the way. His average speed descending was, of course, greater than his average climbing speed.

Prove that there is a spot along the path that the monk will occupy on both trips at precisely the same time of day!

You can probably see why this is true. Can you write a program that computes the time at which the monk will be at the same spot during his ascent and descent?

Input

The input consists of a single test case. The first line contains two integers $a$ ( $0 < a \le 5\,000$ ) and $d$ ( $0 < d \le 5\,000$ ), the number of segments during the ascent and the number of segments during the descent.

The next $a$ lines each contain two integers $h$ ( $0 \le h \le 1\,000$ ) and $t$ ( $0 < t \le 100$ ). $h$ is the positive change in elevation the monk gained during that segment, and $t$ is the time it took. If the monk rests and eats during a segment, $h$ is $0$ .

The last $d$ lines each contain two integers $h$ ( $0 \le h \le 1\,000$ ) and $t$ ( $0 < t \le 100$ ). $h$ is the change in elevation the monk descended during that segment, and $t$ is the time it took. If the monk rests and eats during a segment, $h$ is $0$ .

Output

Output a single floating point number: the earliest point in time at which the monk occupies the same spot during his ascent and his descent. The monk starts both the ascent and the descent at time $0$ .

An answer is correct if its absolute or relative error does not exceed $10^{-5}$ .

Examples3

Example 1
Input
```
1 1
10 11
10 10
```
Expected output
```
5.238095
```
Example 2
Input
```
3 1
4 2
0 3
6 3
10 7
```
Expected output
```
4.200000
```
Example 3
Input
```
3 3
2 3
0 5
3 1
3 4
0 2
2 2
```
Expected output
```
4.000000
```