P15223 [SWERC 2017] 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 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.

The output should be the integer $ L $.

#### Limits - $ 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 $.