부서진 케이크

직사각형 케이크를 트럭에 싣고 식당으로 옮긴다. 가는 길에 트럭이 도로 구멍에 빠지면서 케이크가 완전한 직사각형 조각 $N$개로 부서졌다. $i$번째 조각의 가로 길이는 $w_i$, 세로 길이는 $l_i$이다 ($1 \le i \le N$).

식당에 도착한 손님은 크기가 같은 케이크를 새로 주문하기로 했다. 그런데 원래 주문서를 끝까지 채우지 않아서 케이크의 가로 길이 $W$만 남아 있다. 다행히 부서진 조각은 하나도 잃어버리지 않았다. 조각의 넓이를 모두 더하면 원래 케이크의 넓이와 같다. 케이크의 세로 길이 $L$을 구하라.

조각은 부서지면서 방향이 바뀌었을 수 있다. 즉 $w_i$가 $W$보다 클 수도 있다.

첫째 줄에 케이크의 가로 길이 $W$가 주어진다.

둘째 줄에 부서진 조각의 개수 $N$이 주어진다.

이어지는 $N$개 줄에는 각 조각의 가로 길이 $w_i$와 세로 길이 $l_i$가 공백을 사이에 두고 주어진다.

제한

• $1 \le N \le 5\,000\,000$
• $1 \le W, L \le 10\,000$
• $1 \le w_i, l_i \le 10\,000$ ($1 \le i \le N$)

케이크의 세로 길이 $L$을 정수로 한 줄에 출력한다.