문제

트럭이 직사각형 케이크를 식당으로 운반하고 있습니다. 하지만 가던 중, 푹 패인 구멍에 덜컹거려 케이크가 1 <= i <= N인 i에 대해 가로 w_i 세로 l_i인 직사각형 모양 케이크 조각 N개로 완벽히 갈라졌습니다.

식당에서 피해가 확인되고 고객은 똑같은 크기의 케이크를 다시 주문하기로 했습니다. 하지만 안타깝게도 원래 발주 양식이 제대로 작성되지 않아 케이크의 가로 길이 W만이 확인됩니다. 식당은 당신에게 케이크의 세로 길이 L을 찾아 달라고 부탁합니다. 다행히 케이크 조각은 모두 존재합니다.

입력

입력은 아래의 정수로 구성되어 있습니다:

- 첫 줄에 케이크의 가로 길이 W가 주어집니다;

- 둘째 줄에 조각난 케이크의 수 N이 주어집니다;

- 다음 N개의 줄에, 각 조각의 가로 길이 w_i와 세로 길이 l_i가 주어집니다.

제한

- 1 <= N <= 5,000,000;

- 1 <= W, L <= 10,000;

- 1 <= i <= N인 각 i에 대하여, 1 <= w_i, l_i <= 10,000

출력

정수 L을 출력합니다.