시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 74 27 25 40.984%

문제

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

상근타워에는 엘리베이터가 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+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVkMGMwXHVjNmNjXHVjNzU4IFx1Yjg1Y1x1YmU0NFx1YzVkMCBcdWMxMWNcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzgxYywgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjZThcdWI3N2NcdWMxMWMgXHVkMGMwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViOTdjIFx1ZDBjNCBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViMmU0XHViOTc4IFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yjg1YyBcdWJjMTRcdWFmZDRcdWQwYzggXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzAgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBuXHViYzg4IFx1YjIwY1x1YjdlY1x1YzExYyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMGFlXHVjNzQwIFx1Y2UzNShcdWI4NWNcdWJlNDRcdWIyOTQgXHVjODFjXHVjNjc4KVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1YWNmYyBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMSwwMDAsMDAwLCAxICZsZTsgbSAmbGU7IDIsMDAwKSBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWJjODRcdWQyYmMgdTxzdWI+aTxcL3N1Yj5cdWM2NDAgZDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IHU8c3ViPmk8XC9zdWI+LCBkPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViOTdjIFx1ZDBjMFx1YWNlMCBcdWJjODRcdWQyYmNcdWM3NDQgblx1YmM4OCBcdWIyMGNcdWI3ZWNcdWMxMWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjBhZVx1Yzc0MCBcdWNlMzVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM1NDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCdXNpbmVzcyBDZW50ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkludGVybmF0aW9uYWwgQ3liZXIgUG9saWNlIENvcnBvcmF0aW9uIChJQ1BDKSBoYWQgYnVpbHQgYSBuZXcgbWVnYS10YWxsIGJ1c2luZXNzIGNlbnRlciB0byBob3N0IGl0cyBoZWFkcXVhcnRlcnMgYW5kIHRvIGxlYXNlIHNvbWUgc3BhY2UgZm9yIGV4dHJhIHByb2ZpdC4gSXQgaGFzIHNvIG1hbnkgZmxvb3JzLCB0aGF0IGl0IGlzIGltcHJhY3RpY2FsIHRvIGhhdmUgYSBzZXBhcmF0ZSBidXR0b24gaW4gZWFjaCBvZiBpdHMgbSBlbGV2YXRvciBjYXJzIGZvciBlYWNoIGluZGl2aWR1YWwgZmxvb3IuIEluc3RlYWQsIGVhY2ggZWxldmF0b3IgY2FyIGhhcyBqdXN0IHR3byBidXR0b25zLiBPbmUgYnV0dG9uIGluIGktdGggZWxldmF0b3IgY2FyIG1ha2VzIGl0IG1vdmUgdXAgdTxzdWI+aTxcL3N1Yj4gZmxvb3JzLCB0aGUgb3RoZXIgbWFrZXMgaXQgbW92ZSBkb3duIGQ8c3ViPmk8XC9zdWI+IGZsb29ycy4gVGhlIGJ1c2luZXNzIGNlbnRlciBpcyBzbyBoaWdoLCB0aGF0IHdlIGNhbiBpZ25vcmUgaXRzIGhlaWdodCBmb3IgdGhpcyBwcm9ibGVtICh5b3Ugd2lsbCBuZXZlciByZWFjaCB0aGUgdG9wIGZsb29yKSwgYnV0IHlvdSBjYW5ub3QgZ28gYmVsb3cgdGhlIGdyb3VuZCBmbG9vci4gQWxsIGZsb29ycyBhcmUgbnVtYmVyZWQgYnkgaW50ZWdlciBudW1iZXJzIHN0YXJ0aW5nIGZyb20gemVybywgemVybyBiZWluZyB0aGUgZ3JvdW5kIGZsb29yLjxcL3A+XHJcblxyXG48cD5Zb3Ugc3RhcnQgb24gdGhlIGdyb3VuZCBmbG9vciBvZiB0aGUgYnVzaW5lc3MgY2VudGVyLiBZb3UgaGF2ZSB0byBjaG9vc2Ugb25lIGVsZXZhdG9yIGNhciBvdXQgb2YgbSB0byByaWRlIG9uLiBZb3UgY2Fubm90IHN3aXRjaCBlbGV2YXRvcnMgY2FycyBhZnRlciB0aGF0LiBXaGF0IGlzIHRoZSBsb3dlc3QgZmxvb3IgYWJvdmUgdGhlIGdyb3VuZCBmbG9vciB5b3UgY2FuIGdldCB0byBhZnRlciB5b3UgcHJlc3MgZWxldmF0b3IgY2FyIGJ1dHRvbnMgZXhhY3RseSBuIHRpbWVzPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVycyBuIGFuZCBtICgxICZsZTsgbiAmbGU7IDEgMDAwIDAwMCwgMSAmbGU7IG0gJmxlOyAyIDAwMCkgLSB0aGUgbnVtYmVyIG9mIGJ1dHRvbiBwcmVzc2VzIGFuZCB0aGUgbnVtYmVyIG9mIGVsZXZhdG9yIGNhcnMgdG8gY2hvb3NlIGZyb20uIFRoZSBmb2xsb3dpbmcgbSBsaW5lcyBkZXNjcmliZSBlbGV2YXRvciBjYXJzLiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVycyB1PHN1Yj5pPFwvc3ViPiBhbmQgZDxzdWI+aTxcL3N1Yj4gKDEgJmxlOyB1PHN1Yj5pPFwvc3ViPiwgZDxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+V3JpdGUgdG8gdGhlIG91dHB1dCBmaWxlIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbnVtYmVyIC0gdGhlIG51bWJlciBvZiB0aGUgbG93ZXN0IGZsb29yIGFib3ZlIGdyb3VuZCBmbG9vciB0aGF0IGNhbiBiZSByZWFjaGVkIGJ5IG9uZSBvZiBtIGVsZXZhdG9ycyBhZnRlciBwcmVzc2luZyBpdHMgYnV0dG9ucyBleGFjdGx5IG4gdGltZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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