Problem J
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\leqslant i\leqslant 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\leqslant N\leqslant 5\, 000\, 000$;
-
$1\leqslant W,L \leqslant 10\, 000$;
-
for each $1\leq i\leq N$, $1\leqslant w_ i,l_ i \leqslant 10\, 000$.
Output
The output should be the integer $L$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 7 2 3 1 4 1 2 1 2 2 2 2 2 2 1 |
6 |
