Space Golf

A new scheme for exploring a planet surface uses projectiles nicknamed observation bullets instead of rover type explorers. A bullet has no mobile ability of its own, which is what makes it so much cheaper.

A launcher shoots a bullet with an initial velocity. The bullet then flies along a parabola until it touches down. It bounces on the surface and flies along another parabola, and this repeats virtually forever.

We want a bullet to bounce precisely on the target spot of the planet surface, and we set its initial velocity to make that happen. At the instant of that bounce the sensors inside the bullet gather data and send it to the observation base. This may sound like ordinary target shooting, but several issues make it harder.

• There may be obstacles between the launcher and the target spot. An obstacle stands upright and is thin enough that we ignore its width. Once the bullet touches an obstacle its trajectory afterwards is unknown, so the launch has to avoid every obstacle.
• Shooting the bullet almost vertically at a high enough speed hits the target without touching any obstacle, but a high initial speed consumes energy. Energy is extremely precious in space exploration, so the initial speed of the bullet has to be minimized. Making the bullet bounce a number of times brings it to the target at a lower initial speed.
• The bullet cannot bounce more times than a given limit. The body of the bullet is strong enough, but some of the sensors inside do not stand repeated shocks. The allowed number of bounces varies with the type of the observation bullet.

Write a program that reports the minimum initial speed the mission needs.

Assume the following.

• The atmosphere of the planet is so thin that atmospheric resistance is ignored.
• The planet is large enough that its surface is a completely flat plane.
• The gravity acceleration is constant up to the highest point a bullet reaches.

So the bullets fly along a perfect parabolic trajectory.

Assume the following as well.

• The surface of the planet and the bullets are so hard that a bounce is an elastic collision. In other words, the kinetic energy lost on a bounce is ignored. Atmospheric resistance is ignored too, so the velocity of a bullet immediately after a bounce equals the velocity immediately after its launch.
• A bullet is compact enough that its size is ignored.
• The launcher is compact enough that its height is ignored.

Here are the basics of rigid body dynamics.

Describe the velocity $v$ of the bullet with its horizontal component $v_x$ and its vertical component $v_y$, where positive means upward. The initial velocity has the components $v_{ix}$ and $v_{iy}$, so immediately after the launch $v_x = v_{ix}$ and $v_y = v_{iy}$ hold. At time $t$, write the horizontal distance of the bullet from the launcher as $x$ and its altitude as $y$.

The horizontal velocity component stays constant during the flight when atmospheric resistance is ignored. The horizontal distance from the launcher is therefore proportional to the time elapsed.

$x = v_{ix} t$

The vertical velocity component $v_y$ is gradually decelerated by the gravity. With the gravity acceleration $g$, this differential equation holds during the flight.

$\frac{dv_y}{dt} = -g$

Solving it with the initial conditions $v_y = v_{iy}$ and $y = 0$ at $t = 0$ gives the following.

$y = -\frac{1}{2} g t^2 + v_{iy} t = -\left( \frac{1}{2} g t - v_{iy} \right) t$

That equation says the bullet reaches the ground again at $t = 2 v_{iy} / g$. The point of the bounce is thus at distance $2 v_{ix} v_{iy} / g$ from the launcher. In other words, to make the bullet fly the distance $l$, the two components of the initial velocity satisfy $2 v_{ix} v_{iy} = l g$.

Eliminating the parameter $t$ from the two equations above gives the equation of the parabolic trajectory of the bullet.

$y = -\frac{g}{2 v_{ix}^2} x^2 + \frac{v_{iy}}{v_{ix}} x$

For ease of computation this problem uses a special unit system, in which the gravity acceleration $g$ of the planet is exactly 1.0.

The input is a single test case in the following format.

d n b
p1 h1
p2 h2
.
.
.
pn hn

The first line contains three integers $d$, $n$, and $b$. Here $d$ is the distance from the launcher to the target spot ($1 \le d \le 10000$), $n$ is the number of obstacles ($1 \le n \le 10$), and $b$ is the maximum number of bounces allowed ($0 \le b \le 15$). The bounce at the target spot is not counted in that number.

Each of the following $n$ lines has two integers. On the $k$-th line, $p_k$ is the position of the $k$-th obstacle, its distance from the launcher, and $h_k$ is its height from the ground level. For $k = 1, \dots, n-1$, $0 < p_1$ and $p_k < p_{k+1}$ hold, and $p_n < d$. For $k = 1, \dots, n$, $1 \le h_k \le 10000$ holds.

Print the smallest initial speed $v_i$ that makes the bullet reach the target. The initial speed of the bullet is defined as follows.

$v_i = \sqrt{v_{ix}^{2} + v_{iy}^{2}}$

Round the value at the sixth digit after the decimal point and print it on one line with exactly five digits after the decimal point.