상근타워

상근이는 남은 돈으로 매우 높은 빌딩 “상근타워”를 지었다.

상근타워에는 엘리베이터가 $m$개 있다. 각 엘리베이터에는 버튼이 두 개 있다. $i$번째 엘리베이터의 한 버튼은 위로 $u_i$층 올라가는 버튼이고, 다른 버튼은 아래로 $d_i$층 내려가는 버튼이다.

상근타워의 가장 아래층(로비)은 0층이고, 그 위층부터는 1층, 2층과 같이 증가하는 자연수로 번호가 매겨진다. 엘리베이터를 타고 0층보다 아래(지하)로는 내려갈 수 없으며, 건물은 매우 높아 위로는 끝이 없다고 가정한다.

상근이는 로비에 서 있다. 이제 엘리베이터 하나를 골라서 탄다. 한 번 엘리베이터를 타면 다른 엘리베이터로 갈아탈 수 없다. 고른 엘리베이터의 버튼을 정확히 $n$번 눌러서 도달할 수 있는 가장 낮은 층(로비 제외)을 구하는 프로그램을 작성하시오.

첫째 줄에 $n$과 $m$이 주어진다. ($1 \le n \le 1{,}000{,}000$, $1 \le m \le 2{,}000$) 다음 $m$개 줄에는 각 엘리베이터의 $u_i$와 $d_i$가 공백으로 구분되어 주어진다. ($1 \le u_i, d_i \le 1{,}000$)

엘리베이터의 버튼을 정확히 $n$번 눌러서 도달할 수 있는 가장 낮은 층을 출력한다. 단, 로비(0층)는 제외한다.