Description

Pizza is awesome.

After a programming competition, you and your fellow competitors have pizza for lunch. It's much better than the leftovers in your fridge. You are in charge of slicing and distributing the pizzas, which are of various initial areas. You may cut each pizza however you like, and as many times as you would like; you could even not cut a pizza at all, and make the whole thing one big "slice". (Yummy.) The only portioning requirement is that each person receive exactly one slice of pizza, and they can't share it.

These pizzas are rectangular pizzas, like the Detroit style deep dish pizzas from Little Caesars. Weird.

You consider how large of a slice you can guarantee, such that each person gets at least that much. For example, if there are three people, and three pizzas with areas 1, 2, and 3, you can cut the largest pizza in half, yielding slices of area 1, 2, 1.5, and 1.5. That guarantees each person a slice of size 1.5 or more.

Given that you can cut pizzas however you like, what is largest area slice you can guarantee to everyone?

Input

The first line is two numbers separated by a space, M and N. M is the number of people (0 < M < 1000). N is the number of whole pizzas (0 < N < 1000).

The next N lines contain two numbers W and H, the width and height of the pizzas, which are positive integers less than 1000.

Output

Output the maximum area of pizza slice you can guarantee to each person. Your answer must be accurate to within 0.001.

Examples

Input:
3 3
1 1
1 2
3 1

Output
1.5

Input:
3 4
1 1
2 1
1 3
2 2

Output
2

Input:
5 5
1 3
2 1
2 3
7 1
1 11

Output
3.667