Barrel

Time limit1sMemory limit128 MB

Summary

Simulate cubes floating or sinking in a barrel of water and compute the final water level using a binary search or iterative physics-based calculation.

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

Problem

Some amount of water is poured into a barrel, then several cubes of different size and density are placed into the water. Finally, a lid is put on the barrel and pushed down until it rests on the rim of the barrel.

Write a program that computes the resulting water level in the barrel.

You may assume that:

the density of water is 1.0,
the effect of air can be neglected,
every cube fits completely inside the barrel,
the cubes do not rotate and do not touch one another.

Input

The first line contains three real numbers: the base area of the barrel $S$ $(0 < S \le 1000)$ , the height of the barrel $H$ $(0 < H \le 1000)$ , and the volume of water $V$ $(0 < V \le S \cdot H)$ .

The second line contains the number of cubes $N$ $(0 < N \le 1000)$ .

Each of the following $N$ lines contains two real numbers describing one cube: the side length $L$ $(0 < L \le 1000)$ and the density $D$ $(0 < D \le 10)$ .

Output

Print a single line containing the resulting water level, rounded to exactly four decimal places.

Examples7

Example 1
Input
```
100 10 500
1
1 0.5
```
Expected output
```
5.0050
```
Example 2
Input
```
100 10 500
1
2 0.5
```
Expected output
```
5.0400
```
Example 3
Input
```
100 10 500
1
2 2.0
```
Expected output
```
5.0800
```
Example 4
Input
```
100 10 42
1
4 3.0
```
Expected output
```
0.5000
```
Example 5
Input
```
100 10 96
1
2 0.9
```
Expected output
```
1.0000
```
Example 6
Input
```
100 3 244
1
2 0.1
```
Expected output
```
2.5000
```

Example 7

Input

200 20 1000
3
2 0.5
2 2.0
2 0.25

Expected output

5.0700