Problem Description

WLP has recently become obsessed with an online multiplayer battle game (finally understanding why JOHNKRAM spends so much time on Luogu). However, he is troubled because his shipyard and warehouse by the sea are frequently raided by the enemy. Therefore, WLP, using his robust and well-rounded brain (perhaps leaning more towards the former), came up with a great idea. He divided the beach into several columns perpendicular to the coastline and placed several signal towers on some of these columns to monitor the entire beach. However, WLP is an impatient person, and after building the signal towers, he realized that they need power supply to be operational (isn't that obvious?). Each signal tower has a working radius, within which all enemies are under surveillance. WLP discovered that the enemies are very cunning; unless he completely blocks the path, the enemies can take a path of any curvature (not necessarily through whole points, but will not cross the boundary formed by the 0th and Nth columns) to raid his property.

Thus, WLP pondered: What should be the minimum working radius for each signal tower to completely block the path from the beach to the inland? He used his robust and well-rounded brain during a math class and eventually, still couldn't figure it out. So, he sought help from the divine LZZ.

Finally, under WLP's pleading (" %^!@#!(*^!#@$^& (omitting countless cute scenes)"), LZZ wrote a program that solved the problem in a second. However, the wicked LZZ decided to share this difficult problem with countless innocent OIers, and now it's your turn.

Input Format

The first line contains two integers \( N \) and \( M \), representing the number of columns the beach is divided into \( 0, 1, 2, \cdots, N \) and the number of signal towers.

From the second to the \( M+1 \)-th line, each line contains two numbers \( X_i \) and \( Y_i \), indicating the column number and the distance from the beach of the \( i \)-th signal tower.

Output Format

A single line with a real number, representing the minimum working radius, rounded to two decimal places.

Sample Input and Output

Sample Input #1

5 5
1 5
3 5
5 5
4 30
2 15

Sample Output #1

1.00

Sample Input #2

100 2
30 50
90 100

Sample Output #2

39.05

Notes

Data Range and Constraints

• For 10% of the data: \( 1 \le M \le 10 \), \( 1 \le Y_i \le 100 \);
• For 30% of the data: \( 1 \le M \le 50 \), \( 1 \le Y_i \le 1,000 \);
• For 80% of the data: \( 1 \le M \le 500 \), \( 1 \le Y_i \le 1,000 \);
• For 100% of the data: \( 1 \le M \le 800 \), \( 1 \le N \le 1000 \), \( 1 \le X_i \le N \), \( 1 \le Y_i \le 100,000 \).

Hints

Note that blocking the beach means the depth of enemy penetration is limited. If enemies bypass all signal towers and can advance directly, it indicates that the path is not completely blocked.

见题面 Input 部分

见题面 Output 部分