Problem G
Shattered Cake

A rectangular cake is transported via a truck to a restaurant. On the way to the destination, the truck hits a pothole, which shatters the cake into $N$ perfectly rectangular pieces of width $w_i$ and length $l_i$, for $1⩽i⩽N$.

At the destination, the damage is assessed, and the customer decides to order a replacement cake of the same dimensions. Unfortunately, the original order form was incompletely filled and only the width $W$ of the cake is known. The restaurant asks for your help to find out the length $L$ of the cake. Fortunately, all pieces of the shattered cake have been kept.

Input

The input consists of the following integers:

• on the first line, the width $W$ of the cake;

• on the second line, the number $N$ of shattered pieces;

• on each of the next $N$ lines, the width $w_i$ and length $l_i$ of each piece.

Limits

• $1⩽N⩽5000000$;

• $1⩽W,L⩽10000$;

• for each $1\le i\le N$, $1⩽w_i,l_i⩽10000$.

Output

The output should be the integer $L$.

4
7
2 3
1 4
1 2
1 2
2 2
2 2
2 1

6