Link is developing a game. In this game, players can craft things using various types of resources, and things crafted can also be used to craft other things.

Formally speaking, there are  types of items, numbered from  to , and  recipes in the game. In the -th recipe, players can use  items of the -th type to craft  items of the -th type, where  can be any positive real number.

One day, he finds that one player owns more than 18,446,744,073,709,551,615 identical items, which causes a server crash. This is obviously impossible without using glitches.

Link soon finds out that there is something wrong with the crafting recipe. Players may get infinite resources by crafting some special things over and over again!

Link doesn't want to adjust the recipes one by one, so he simply added an argument . Now players can use  items of the -th type to craft  items of the -th type.

Link wonders: What's the maximum  that he can set so that no player can get infinite items by crafting things over and over again?

输入描述:

The first line contains two integers , which are the number of item types and the number of recipes.

Each of the next  lines contains four integers , describing a recipe.

It is guaranteed that players can get infinite items using the recipes above (when ).

输出描述:

Output a real number , which is the maximum  satisfying the condition.

Your answer is considered correct if its absolute or relative error does not exceed .

Formally, let your answer be , and the jury's answer be . Your answer is accepted if and only if .

3 3
1 1 2 2
1 2 2 1
1 3 1 1

0.5000000000

备注:

In the first example:

When , players can use 1 item of the first type to get 2 items of the second type. Then use 2 items of the second type to get 4 items of the first type. Thus, players got 4 items of the first type from 1 item of the first type. By doing so repeatedly, players can get infinite items of the first type, so  does not satisfy the condition. It can be shown that  is the maximum possible .

Note that players can never get infinite items of the third type. But that doesn't matter, you must make sure that players can't get infinite items of any type.