Shattered Cake

A rectangular cake travels to a restaurant on a truck. On the way the truck hits a pothole, and the cake shatters into $N$ perfectly rectangular pieces. Piece $i$ has width $w_i$ and length $l_i$ for $1 \le i \le N$.

At the restaurant the customer orders a replacement cake of the same size. The original order form was left unfinished, so only the width $W$ of the cake is known. Every piece of the shattered cake was kept, so the areas of the pieces add up to the area of the original cake. Find the length $L$ of the cake.

A piece may have turned while the cake broke, so $w_i$ can be larger than $W$.

The first line contains the width $W$ of the cake.

The second line contains the number $N$ of shattered pieces.

Each of the next $N$ lines contains the width $w_i$ and the length $l_i$ of one piece, separated by a space.

Limits

• $1 \le N \le 5\,000\,000$
• $1 \le W, L \le 10\,000$
• $1 \le w_i, l_i \le 10\,000$ for each $1 \le i \le N$

Print the length $L$ of the cake as an integer on one line.