题目描述

Everyone loves chocolate chip cookies! Which unfortunately means sharing sometimes. In this case, you have generously agreed to split a square chocolate chip cookie with your friend.

Because it is your cookie, you get to choose how to cut the cookie, and which piece to give to your friend. You can split the cookie along any straight line that passes through the cookie; the line need not be axis-aligned.

You know the location of all chocolate chips in the cookie. Because you prefer a cookie that is dense with chocolate chips, you want to optimize your cut to produce the best possible split. You accomplish this by maximizing the difference between the fraction of chocolate chips in your piece and the fraction of cookie area in your piece.

输入格式

The first line of input contains two space-separated integers $n$ ($2 \le n \le 10{,}000$) and $m$ ($1 \le m \le 3{,}000$), where $n$ is the side length of the square cookie, and $m$ is the number of chocolate chips in the cookie.

The next $m$ lines each contain two space-separated integers $x$ and $y$ ($0 < x, y < n$) defining the location of a chocolate chip in the cookie. All chocolate chip locations are distinct. If a chocolate chip lies exactly on the cut, you can decide which piece of the cookie it goes to.

输出格式

Output a real number, which is the maximum possible value for $\frac{b}{m} - \frac{a}{n^2}$, where $a$ is the area of cookie that you get, and $b$ is the number of chocolate chips in your piece of the cookie. The answer is accepted with absolute or relative error at most $10^{-6}$.

5 8
1 1
1 2
1 3
2 1
3 1
3 4
4 1
4 2

0.375

提示

:::align{center}

Illustration of Sample Case 1. :::