Empire Strikes Back

Limits: 3 sec., 256 MiB

Empire just discovered that rebel leadership gathered at Lvivooine, so they must act quickly to eliminate the threat. Unfortunately, Empire is in a pretty bad recession right now, so there aren’t any Death Stars left around. Therefore, their plan involves dropping several containers with deadly viruses onto the planet surface.

To make things simpler for you, we will model this problem in 2D. Lvivooine has radius R and is centered at (0,0). There are K Empire spaceships, each of which will simultaneously launch a rocket with a container towards point (0, 0). None of the ships is located within a plante, but it’s possible for two ships to be located at the same point. Once the rocket hits the surface of the planet, virus will start spreading along the surface. Each spaceship has a custom rocket speed, and each virus has a custom spread speed. Note that virus spreads along the surface of the planet - it cannot pass through the planet to reach the other end.

Your task is to determine how much time will it take for Lvivooine to become completely infected - i.e. every point on the planet surface was reached by at least one virus.

However, rebels also have L ballistic missiles in their disposal. These missiles can be used to destroy Empire rockets before they reach the surface - one missle can destroy one rocket. Since rebels are human beings, they want to live as long as possible, so they will destroy the rockets that allow them to extend their miserable lives for as long as possible (meaning they will shot the rockets in such a way that the infection time becomes as big as possible).

Find out how long do the rebels have before they suffocate, and may the force be with you!

Input

First line contains three integers: R - the radius of the planet (in meters), K - the number of spacecrafts, and L - the number or rebel missiles. The next K lines each contain 4 integers: X-coordinate of the ship, Y-coordinate of the ship, rocket speed and virus spead speed (in meters per second). It is guaranteed that no ships are inside the planet.

Output

Print one real number - the time it takes for the planet to become completely infected. Your answer will be considered correct if it is within \(0.0001 (10^-4)\) from the jury answer by either absolute or relative measuring.

Constraints

Both speeds (rocket speed and virus spread speed) are integers between 1 and 1000000, both coordiantes are integers between -1000000 and 1000000, R is an integer between 1 and 1000000. K is an integer between 1 and 10000, L is an ineteger between 0 and 10000, L is strictly less than K.

Samples

Input (stdin) сopy	Output (stdout) сopy
100 1 0 200 0 10 7	54.8798950513

Input (stdin) сopy	Output (stdout) сopy
100 3 2 200 0 10 7 150 0 10 7 -150 0 10 7	54.8798950513

Notes

In the first sample, rebels have no missiles, so the only rocket will hit the planet at (100, 0). The virus spreads both ways, so the total distance to be covered in each way is \(\pi * R\), meaning the answer is \(10 + \pi * 100 / 7\) - the time for the rocket to reach the planet plus the time to spread. In the second sample, it’s optimal for rebels to destroy rockets 2 and 3. After that, we get the same testcase as the first sample. If rebels destroyed other rockets, they would die sooner.