Імперія наносить удар

Обмеження: 3 сек., 256 МіБ

Імперія знайшла центр повстанців на планеті Львівуїн і планує його знищити. На жаль, економіка імперії в поганому стані, і жодної Зорі Смерті наразі немає, тому вони планують скинути на планету декілька контейнерів зі смертельним вірусом.

Для простоти ми змоделюємо цю задачу у 2D. Львівуїн має радіус \(r\) і його центр є в точці (0, 0). У імперії є \(k\) зорельотів, кожен із яких одночасно стріляє в точку (0, 0) ракетою з отруйним контейнером. Жоден із зорельотів не є всередині планети (але декілька зорельотів можуть бути в одній точці). Коли ракета стукнеться об поверхню планети, вірус почне розповсюджуватись уздовж поверхні планети (в обидві сторони). Кожна ракета має свою швидкість, а також кожен вірус має свою швидкість розповсюдження. Зауважте, що вірус розповсюджується вздовж поверхні та не може проникати через планету.

Вам потрібно знайти, за скільки часу Львівуїн буде повністю зараженим, тобто вірус досягне кожної точки планети.

Проте у повстанців є \(l\) снарядів, кожним із яких вони можуть збити рівно одну ракету. Оскільки повстанці — люди та хочуть жити, вони будуть знищувати ракети імперії таким чином, щоб відтермінувати момент повного зараження на якомога більший час.

Знайдіть, скільки часу лишилось жити ганебним повстанцям та хай прибуде з вами сила!

Вхідні дані

Перший рядок містить три цілих числа \(r\) — радіус планети в метрах, \(k\) — кількість ракет і \(l\) — кількість снарядів у повстанців.

Наступні \(k\) рядків містять по 4 цілих числа: \(x\)-координату ракети, \(y\)-координату ракети, швидкість ракети та швидкість поширення вірусу (в метрах на секунду).

Вихідні дані

Виведіть одне число — час до повного зараження планети (в секундах).

Ваша відповідь буде вважатись правильною, якщо абсолютна або відносна похибка від правильної відповіді буде не більшою за \(10^{-4}\).

Обмеження

\(1 \le r \le 10^6\),

\(0 \le l < k \le 10^4\),

\(|x|, |y| \le 10^6\),

обидві швидкості — це цілі числа від 1 до \(10^6\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
100 1 0 200 0 10 7	54.8798950513

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
100 3 2 200 0 10 7 150 0 10 7 -150 0 10 7	54.8798950513

Примітки

У першому прикладі ракета зіткнеться з планетою в точці (100, 0). Вірус піде в два боки, тому йому потрібно подолати \(\pi r\) з кожної сторони для повного зараження. Відповідь: \(10 + \frac{100\pi}{7}\) — час польоту ракети плюс час зараження.

У другому прикладі потрібно збити ракети 2 і 3.