시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 71 25 23 39.655%

문제

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

상근타워에는 엘리베이터가 m개가 있다. 각 엘리베이터에는 두 버튼이 있다. i번째 엘리베이터의 한 버튼은 ui 층을 올라가는 버튼이고, 다른 버튼은 di층 내려가는 버튼이다.

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

상근이는 상근타워의 로비에 서있다. 이제, 엘리베이터중 하나를 골라서 타려고 한다. 엘리베이터를 탄 이후에는 다른 엘리베이터로 바꿔탈 수 없다. 이 때, 엘리베이터 버튼을 정확하게 n번 눌러서 갈 수 있는 가장 낮은 층(로비는 제외)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n과 m이 주어진다. (1 ≤ n ≤ 1,000,000, 1 ≤ m ≤ 2,000) 다음 m개 줄에는 각 엘리베이터의 버튼 ui와 di가 주어진다. (1 ≤ ui, di ≤ 1000)

출력

엘리베이터를 타고 버튼을 n번 눌러서 갈 수 있는 가장 낮은 층을 출력한다.

예제 입력 1

10 3
15 12
15 4
7 12

예제 출력 1

13

힌트

W3sicHJvYmxlbV9pZCI6IjM1NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWQwYzBcdWM2Y2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIwYThcdWIyOTQgXHViM2M4XHVjNzNjXHViODVjIFx1YjllNFx1YzZiMCBcdWIxOTJcdWM3NDAgXHViZTRjXHViNTI5ICZxdW90O1x1YzBjMVx1YWRmY1x1ZDBjMFx1YzZjYyZxdW90O1x1Yjk3YyBcdWM5YzBcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1ZDBjMFx1YzZjY1x1YzVkMFx1YjI5NCBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWFjMDAgbVx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YmM4NFx1ZDJiY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHVjNzU4IFx1ZDU1YyBcdWJjODRcdWQyYmNcdWM3NDAgdTxzdWI+aTxcL3N1Yj4gXHVjZTM1XHVjNzQ0IFx1YzYyY1x1Yjc3Y1x1YWMwMFx1YjI5NCBcdWJjODRcdWQyYmNcdWM3NzRcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWJjODRcdWQyYmNcdWM3NDAgZDxzdWI+aTxcL3N1Yj5cdWNlMzUgXHViMGI0XHViODI0XHVhYzAwXHViMjk0IFx1YmM4NFx1ZDJiY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVkMGMwXHVjNmNjXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI3OThcdWNlMzUoXHViODVjXHViZTQ0KVx1Yzc0MCAwXHVjZTM1XHVjNzc0XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjIFx1Y2UzNVx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWI5N2MgXHVkMGMwXHVhY2UwIFx1YzljMFx1ZDU1OFx1Yjg1YyBcdWIwYjRcdWI4MjRcdWFjMDggXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVhYzc0XHViYjNjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWIxOTJcdWM1NDQmbmJzcDtcdWIwNWRcdWM3NzQmbmJzcDtcdWM1YzZcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVkMGMwXHVjNmNjXHVjNzU4IFx1Yjg1Y1x1YmU0NFx1YzVkMCBcdWMxMWNcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzgxYywgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjZThcdWI3N2NcdWMxMWMgXHVkMGMwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViOTdjIFx1ZDBjNCBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViMmU0XHViOTc4IFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yjg1YyBcdWJjMTRcdWFmZDRcdWQwYzggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwIFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgblx1YmM4OCBcdWIyMGNcdWI3ZWNcdWMxMWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjBhZVx1Yzc0MCBcdWNlMzUoXHViODVjXHViZTQ0XHViMjk0IFx1YzgxY1x1YzY3OClcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWFjZmMgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEsMDAwLDAwMCwgMSAmbGU7IG0gJmxlOyAyLDAwMCkgXHViMmU0XHVjNzRjIG1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWM3NTggXHViYzg0XHVkMmJjIHU8c3ViPmk8XC9zdWI+XHVjNjQwIGQ8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB1PHN1Yj5pPFwvc3ViPiwgZDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWQwYzBcdWFjZTAgXHViYzg0XHVkMmJjXHVjNzQ0IG5cdWJjODggXHViMjBjXHViN2VjXHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIwYWVcdWM3NDAgXHVjZTM1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNTQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnVzaW5lc3MgQ2VudGVyIiwiZGVzY3JpcHRpb24iOiI8cD5JbnRlcm5hdGlvbmFsIEN5YmVyIFBvbGljZSBDb3Jwb3JhdGlvbiAoSUNQQykgaGFkIGJ1aWx0IGEgbmV3IG1lZ2EtdGFsbCBidXNpbmVzcyBjZW50ZXIgdG8gaG9zdCBpdHMgaGVhZHF1YXJ0ZXJzIGFuZCB0byBsZWFzZSBzb21lIHNwYWNlIGZvciBleHRyYSBwcm9maXQuIEl0IGhhcyBzbyBtYW55IGZsb29ycywgdGhhdCBpdCBpcyBpbXByYWN0aWNhbCB0byBoYXZlIGEgc2VwYXJhdGUgYnV0dG9uIGluIGVhY2ggb2YgaXRzIG0gZWxldmF0b3IgY2FycyBmb3IgZWFjaCBpbmRpdmlkdWFsIGZsb29yLiBJbnN0ZWFkLCBlYWNoIGVsZXZhdG9yIGNhciBoYXMganVzdCB0d28gYnV0dG9ucy4gT25lIGJ1dHRvbiBpbiBpLXRoIGVsZXZhdG9yIGNhciBtYWtlcyBpdCBtb3ZlIHVwIHU8c3ViPmk8XC9zdWI+IGZsb29ycywgdGhlIG90aGVyIG1ha2VzIGl0IG1vdmUgZG93biBkPHN1Yj5pPFwvc3ViPiBmbG9vcnMuIFRoZSBidXNpbmVzcyBjZW50ZXIgaXMgc28gaGlnaCwgdGhhdCB3ZSBjYW4gaWdub3JlIGl0cyBoZWlnaHQgZm9yIHRoaXMgcHJvYmxlbSAoeW91IHdpbGwgbmV2ZXIgcmVhY2ggdGhlIHRvcCBmbG9vciksIGJ1dCB5b3UgY2Fubm90IGdvIGJlbG93IHRoZSBncm91bmQgZmxvb3IuIEFsbCBmbG9vcnMgYXJlIG51bWJlcmVkIGJ5IGludGVnZXIgbnVtYmVycyBzdGFydGluZyBmcm9tIHplcm8sIHplcm8gYmVpbmcgdGhlIGdyb3VuZCBmbG9vci48XC9wPlxyXG5cclxuPHA+WW91IHN0YXJ0IG9uIHRoZSBncm91bmQgZmxvb3Igb2YgdGhlIGJ1c2luZXNzIGNlbnRlci4gWW91IGhhdmUgdG8gY2hvb3NlIG9uZSBlbGV2YXRvciBjYXIgb3V0IG9mIG0gdG8gcmlkZSBvbi4gWW91IGNhbm5vdCBzd2l0Y2ggZWxldmF0b3JzIGNhcnMgYWZ0ZXIgdGhhdC4gV2hhdCBpcyB0aGUgbG93ZXN0IGZsb29yIGFib3ZlIHRoZSBncm91bmQgZmxvb3IgeW91IGNhbiBnZXQgdG8gYWZ0ZXIgeW91IHByZXNzIGVsZXZhdG9yIGNhciBidXR0b25zIGV4YWN0bHkgbiB0aW1lcz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgbiBhbmQgbSAoMSAmbGU7IG4gJmxlOyAxIDAwMCAwMDAsIDEgJmxlOyBtICZsZTsgMiAwMDApIC0gdGhlIG51bWJlciBvZiBidXR0b24gcHJlc3NlcyBhbmQgdGhlIG51bWJlciBvZiBlbGV2YXRvciBjYXJzIHRvIGNob29zZSBmcm9tLiBUaGUgZm9sbG93aW5nIG0gbGluZXMgZGVzY3JpYmUgZWxldmF0b3IgY2Fycy4gRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgdTxzdWI+aTxcL3N1Yj4gYW5kIGQ8c3ViPmk8XC9zdWI+ICgxICZsZTsgdTxzdWI+aTxcL3N1Yj4sIGQ8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPldyaXRlIHRvIHRoZSBvdXRwdXQgZmlsZSBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG51bWJlciAtIHRoZSBudW1iZXIgb2YgdGhlIGxvd2VzdCBmbG9vciBhYm92ZSBncm91bmQgZmxvb3IgdGhhdCBjYW4gYmUgcmVhY2hlZCBieSBvbmUgb2YgbSBlbGV2YXRvcnMgYWZ0ZXIgcHJlc3NpbmcgaXRzIGJ1dHRvbnMgZXhhY3RseSBuIHRpbWVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Northeastern European Regional Contest > NEERC 2009 B번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: movie_jo