A cake fit for a king ~wleung_bvg.

Everybody knows that cake comes in two shapes, circular or rectangular.
Everybody except for Wesley.

In his defence:

You wouldn't buy a rectangular shaped pizza would you?

Thus Wesley has only ever cut his cake in one way.

• Imagine a Cartesian grid over the center of the cake labelled at $(0,0)$.
• Make $M$ cuts over the line formed by $y=m_{i}x$ within the cake's boundaries.

With Wesley's birthday coming up, his friends have decided to play a little prank on him. They have purchased a square shaped cake with side length $2N$ and would like to know the side length of the largest axis-aligned square obtainable that does not intersect with any cut. A square intersects a cut if there is a non-zero area of the square on both sides of the cut. This means that touching a cut does not count as an intersection.

Slope will be given as $a_i,b_i$ where $m_i={\displaystyle \frac{a_i}{b_i}}$.

Input Specification

The first line will contain two integers, $N$ and $M$ $(1\le N\le {10}^3,1\le M\le {10}^5)$, half the length of the cake, and the number of cuts Wesley makes.

The next $M$ lines will each contain two integers, $a_i,b_i$ $(1\le |a_i|,b_i\le {10}^3)$, the numerator and denominator of the slope of the line used to determine the cut. $a_i$ and $b_i$ are guaranteed to be coprime, and the pair $(a_i,b_i)$ is guaranteed to be unique.

Output Specification

Output two positive integers, $n$ and $d$ space-separated on one line. This means the side length of the largest obtainable axis-aligned square is ${\displaystyle \frac{n}{d}}$. Note that $n$ and $d$ must be coprime.

Constraints

Subtask 1 [30%]

$M\le 2$

Subtask 2 [70%]

No additional constraints.

Sample Input 1

1 2
-1 1
1 1

Sample Output 1

2 3

Explanation For Sample 1

The following image shows the cake:

The red square is the cake, and the blue and green lines show the two cuts. The black line shows one of the many different largest squares obtainable.

Sample Input 2

2 2
-1 2
1 1

Sample Output 2

3 2

Sample Input 3

1000 2
-1000 1
1000 1

Sample Output 3

2000000 2001