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 \le i \le 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 Specification

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.

Constraints

~1 \le N \le 5\,000\,000~

~1 \le W, L \le 10\,000~

For each ~1 \le i \le N~, ~1 \le w_i, l_i \le 10\,000~.

Output Specification

The output should be the integer ~L~.

Sample Input

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

Sample Output

6