F - Shattered Cake

Time limit: 10 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

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 in $N$ perfectly rectangular pieces of width $w_i$ and length $l_i$, for $1\leq i\leq 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.


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.


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


The output should be the integer $L$.

Sample test(s)

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