2016 ACM ICPC Asia Nha Trang Regional Contest Replay

Start

2017-10-15 12:00 UTC

2016 ACM ICPC Asia Nha Trang Regional Contest Replay

End

2017-10-15 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 12:36:39

Time elapsed

5:00:00

Time remaining

0:00:00

Problem J
Swimming Balls

To attract more people coming to the pool, the manager puts a number of swimming balls into the pool. He wants to calculate the level of water in the pool after putting $V$ ${m}^{3}$ of water and $n$ given balls into the pool. The ${i}^{th}$ ball is a homogeneous sphere (mass is distributed evenly) having a specific weight (or unit weight) ${w}_{i}$ and a radius ${r}_{i}$. The pool is a rectangle with dimensions $W$ (width) x $L$ (length) x $D$ (depth) in meters. Your task is to calculate the level of water (measured in meters to the bottom of the pool) after putting $V$ ${m}^{3}$ of water and $n$ given balls into the pool. This level of water can be at most $D$.

\includegraphics[width=0.3\textwidth ]{1.jpg}

We assume that the specific weight of water is $1.0$, there is no interaction among the $n$ balls, and the Archimedes’ principle is perfectly guaranteed.

Hints: the volume of a homogeneous sphere having a radius $r$ could be computed using the following formula: $V = \frac{4}{3}\pi {r}^{3}, \pi =3.141592653589793$

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $50$. The following lines describe the datasets.

Each dataset contains the following information:

  • The first line contains five integers $n, W, L, D, V$ $(1 \leq n \leq {10}^{3}, 2 \leq W, L \leq {10}^{3}, D \leq 5, V\leq W*L*D)$.

  • The ${i}^{th}$ line of the $n$ following lines contains two positive floats ${r}_{i}$ and ${w}_{i}$ indicating the specific weight and radius of the ${i}^{th}$ ball $(0 < {w}_{i}, {r}_{i} \leq 2)$

Output

For each dataset, write in one line the number indicating the water level, which should be at most $D$. Your answer is accepted iff it is correct within an absolute or relative error of ${10}^{-4}$.

Sample Input 1 Sample Output 1
2
1 2 2 2 5
1.0 1.0
1 2 2 2 5
0.8 1.0
2.00000000000
1.78616514621