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 wi and length li, for 1 ⩽ i ⩽ N. At the destination, the damage is assessed, and the customer decides to order a replacement cake of the same dimensions. Unfortunately, the original or- der 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 file contains several test cases, each of them as described below. 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 wi and length li of each piece. Limits • 1 ⩽ N ⩽ 5 000 000; • 1⩽W,L⩽10000; • foreach1≤i≤N,1⩽wi,li ⩽10000. Output For each test case, the output should be the integer L, on a line by itself. Sample Input 4 7 23 14 12 12 22 22 21
2/2 Sample Output 6