레이팅 미적용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\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.
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\).
The output should be the integer \(L\).
4
7
2 3
1 4
1 2
1 2
2 2
2 2
2 1
6