시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 543 268 239 51.178%

문제

인기 티비 프로그램 "나는 요리사 인가?"의 새 시즌이 시작한다. 이번 시즌은 기네스북에 등재될 만한 음식을 만드는 것을 목표로 진행한다.

첫 번째 에피소드에 출연하는 요리사는 전설의 요리사 김상근이고, 길이 L미터의 롤 케이크를 만들 것이다.

상근은 몇 시간동안 집중해서 케이크를 만들었고, 이제 스튜디오의 방청객 N명에게 케이크를 나누어 주려고 한다.

상근이는 롤 케이크를 펼쳐서 1미터 단위로 잘라 놓았다. 가장 왼쪽 조각이 1번, 오른쪽 조각이 L번 조각이다. 방청객은 1번부터 N번까지 번호가 매겨져 있다. 각 방청객은 종이에 자신이 원하는 조각을 적어서 낸다. 이 때, 두 숫자 P와 K를 적어서 내며, P번 조각부터 K번 조각을 원한다는 뜻이다.

프로그램의 진행자 고창영은 1번 방청객의 종이부터 순서대로 펼쳐서 해당하는 조각에 그 사람의 번호를 적을 것이다. 이 때, 이미 번호가 적혀있는 조각은 번호를 적지 못하고 넘어간다. 이런 방식을 이용해서 방청객에게 조각을 주다보니, 자신이 원래 원했던 조각을 받지 못하는 경우가 생길 수 있다.

아래 그림은 이 문제의 예제를 나타낸 것이다.

가장 많은 케이크 조각을 받을 것으로 기대한 방청객의 번호와 실제로 가장 많은 케이크 조각을 받는 방청객의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 롤 케이크의 길이 L (1 ≤ L ≤ 1000)이 주어진다. 둘째 줄에는 방청객의 수 N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개 줄에는 각 방청객 i가 종이에 적어낸 숫자 Pi와 Ki가 주어진다. (1 ≤ Pi ≤ Ki ≤ L, i = 1..N)

출력

첫째 줄에 가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호를 출력한다.

둘째 줄에 실제로 가장 많은 조각을 받은 방청객의 번호를 출력한다.

가장 많은 조각을 받거나 예상되는 방청객이 여러 명인 경우에는 번호가 작은 사람을 출력한다.

예제 입력 1

10
3
2 4
7 8
6 9

예제 출력 1

3
1
W3sicHJvYmxlbV9pZCI6IjM5ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NjQgXHVjZjAwXHVjNzc0XHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzhcdWFlMzAgXHVkMmYwXHViZTQ0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCAmcXVvdDtcdWIwOThcdWIyOTQgXHVjNjk0XHViOWFjXHVjMGFjIFx1Yzc3OFx1YWMwMD8mcXVvdDtcdWM3NTggXHVjMGM4IFx1YzJkY1x1Yzk4Y1x1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YmM4OCBcdWMyZGNcdWM5OGNcdWM3NDAgXHVhZTMwXHViMTI0XHVjMmE0XHViZDgxXHVjNWQwIFx1YjRmMVx1YzdhY1x1YjQyMCBcdWI5Y2NcdWQ1NWMgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NDQgXHViYWE5XHVkNDVjXHViODVjIFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM1ZDBcdWQ1M2NcdWMxOGNcdWI0ZGNcdWM1ZDAgXHVjZDljXHVjNWYwXHVkNTU4XHViMjk0IFx1YzY5NFx1YjlhY1x1YzBhY1x1YjI5NCBcdWM4MDRcdWMxMjRcdWM3NTggXHVjNjk0XHViOWFjXHVjMGFjIFx1YWU0MFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWNlMCwgXHVhZTM4XHVjNzc0IExcdWJiZjhcdWQxMzBcdWM3NTggXHViODY0IFx1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NDAgXHViYTg3IFx1YzJkY1x1YWMwNFx1YjNkOVx1YzU0OCBcdWM5ZDFcdWM5MTFcdWQ1NzRcdWMxMWMgXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YWNlMCwgXHVjNzc0XHVjODFjIFx1YzJhNFx1ZDI5Y1x1YjUxNFx1YzYyNFx1Yzc1OCBcdWJjMjlcdWNjYWRcdWFjMWQgTlx1YmE4NVx1YzVkMFx1YWM4YyBcdWNmMDBcdWM3NzRcdWQwNmNcdWI5N2MgXHViMDk4XHViMjA0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI4NjQgXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1ZDNiY1x1Y2NkMFx1YzExYyAxXHViYmY4XHVkMTMwIFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWM3OThcdWI3N2MgXHViMTkzXHVjNTU4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1Yzg3MFx1YWMwMVx1Yzc3NCAxXHViYzg4LCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjODcwXHVhYzAxXHVjNzc0IExcdWJjODggXHVjODcwXHVhYzAxXHVjNzc0XHViMmU0LiBcdWJjMjlcdWNjYWRcdWFjMWRcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViYzI5XHVjY2FkXHVhYzFkXHVjNzQwIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM4MDFcdWM1YjRcdWMxMWMgXHViMGI4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWI0NTAgXHVjMjJiXHVjNzkwIFBcdWM2NDAgS1x1Yjk3YyBcdWM4MDFcdWM1YjRcdWMxMWMgXHViMGI0XHViYTcwLCBQXHViYzg4IFx1Yzg3MFx1YWMwMVx1YmQ4MFx1ZDEzMCBLXHViYzg4IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM2ZDBcdWQ1NWNcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjOWM0XHVkNTg5XHVjNzkwIFx1YWNlMFx1Y2MzZFx1YzYwMVx1Yzc0MCAxXHViYzg4IFx1YmMyOVx1Y2NhZFx1YWMxZFx1Yzc1OCBcdWM4ODVcdWM3NzRcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDNiY1x1Y2NkMFx1YzExYyBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjODcwXHVhYzAxXHVjNWQwIFx1YWRmOCBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzgwMVx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Yzc3NFx1YmJmOCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1Yzg3MFx1YWMwMVx1Yzc0MCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjODAxXHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWNlMCBcdWIxMThcdWM1YjRcdWFjMDRcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWJjMjlcdWMyZGRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YmMyOVx1Y2NhZFx1YWMxZFx1YzVkMFx1YWM4YyBcdWM4NzBcdWFjMDFcdWM3NDQgXHVjOGZjXHViMmU0XHViY2Y0XHViMmM4LCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNmQwXHViNzk4IFx1YzZkMFx1ZDU4OFx1YjM1OCBcdWM4NzBcdWFjMDFcdWM3NDQgXHViYzFiXHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjMGRkXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM2MDhcdWM4MWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9yb2xsLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjY3cHg7IHdpZHRoOjMxN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjZjAwXHVjNzc0XHVkMDZjIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWJjMWJcdWM3NDQgXHVhYzgzXHVjNzNjXHViODVjIFx1YWUzMFx1YjMwMFx1ZDU1YyBcdWJjMjlcdWNjYWRcdWFjMWRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YzJlNFx1YzgxY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWM4NzBcdWFjMDFcdWM3NDQgXHViYzFiXHViMjk0IFx1YmMyOVx1Y2NhZFx1YWMxZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yjg2NCBcdWNmMDBcdWM3NzRcdWQwNmNcdWM3NTggXHVhZTM4XHVjNzc0IEwgKDEgJmxlOyBMICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMyOVx1Y2NhZFx1YWMxZFx1Yzc1OCBcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAxMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYzI5XHVjY2FkXHVhYzFkIGlcdWFjMDAgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1YzViNFx1YjBiOCBcdWMyMmJcdWM3OTAgUGlcdWM2NDAgSzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFA8c3ViPmk8XC9zdWI+ICZsZTsgSzxzdWI+aTxcL3N1Yj4gJmxlOyBMLCBpID0gMS4uTik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmMxYlx1Yzc0NCBcdWFjODNcdWM3M2NcdWI4NWMgXHVhZTMwXHViMzAwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjM1OCZuYnNwO1x1YmMyOVx1Y2NhZFx1YWMxZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJlNFx1YzgxY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWJjMWJcdWM3NDAgXHViYzI5XHVjY2FkXHVhYzFkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmMxYlx1YWM3MFx1YjA5OCBcdWM2MDhcdWMwYzFcdWI0MThcdWIyOTQgXHViYzI5XHVjY2FkXHVhYzFkXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWJhODVcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM3OTFcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTg1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT1JFSE5KQUNBIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVzZSBkYXlzLCB0aGUgVFYgc3R1ZGlvIGhhcyBzdGFydGVkIHNob290aW5nIGFub3RoZXIgbmV3IHNlYXNvbiBvZiBKYW1pZSBPbGl2ZXImIzM5O3MgY29va2luZyBzaG93LiBUaGlzIHNlYXNvbiwgSmFtaWUgcGxhbnMgdG8gaW50cm9kdWNlIHRoZSBkZWxpZ2h0cyBvZiBDcm9hdGlhbiBjdWlzaW5lIHRvIHRoZSB3b3JsZC4gSW4gdGhlIGZpcnN0IGVwaXNvZGUsIHRoZSBtYXN0ZXIgY2hlZiBoYXMgYmFrZWQgYSB3YWxudXQgcm9sbCBMIG1ldGVycyBsb25nLCB0aGUgbG9uZ2VzdCBldmVyIGJha2VkIGluIHRoaXMgcGFydCBvZiB0aGUgd29ybGQuIEFmdGVyIGhvdXJzIG9mIHN3ZWF0aW5nIGFuZCB0b2lsaW5nIGluIHRoZSBraXRjaGVuLCBoZSBoYXMgZGVjaWRlZCB0byByZXdhcmQgZWFjaCBvbmUgb2YgaGlzIE4gZmFpdGhmdWwgc3BlY3RhdG9ycyBpbiB0aGUgc3R1ZGlvLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZSBoYXMgY2hvcHBlZCB0aGUgd2FsbnV0IHJvbGwgaW50byBvbmUgbWV0ZXIgbG9uZyBjaG9wcyBhbmQgbWFya2VkIHRoZW0gd2l0aCBudW1iZXJzIGZyb20gMSBkbyBMLCBmcm9tIGxlZnQgdG8gcmlnaHQuIEVhY2ggc3BlY3RhdG9yIGhhcyByZWNlaXZlZCBhIHVuaXF1ZSBudW1iZXIgSUQgKGEgcG9zaXRpdmUgaW50ZWdlciBmcm9tIDEgdG8gTiksIGFzIHdlbGwgYXMgYSBwYXBlciB3aXRoIHR3byBpbnRlZ2VycywgUCBhbmQgSy4gRWFjaCBzcGVjdGF0b3Igd2FzIHRoZW4gYWxsb3dlZCB0byB0YWtlIGFsbCBjaG9wcyBmcm9tIHRoZSBQLXRoIHRvIHRoZSBLLXRoLCBpbmNsdXNpdmUuIFNwZWN0YXRvcnMgd2VyZSBhbGxvd2VkIHRvIHRha2UgdGhlaXIgc2hhcmUgaW4gb3JkZXIgb2YgdGhlaXIgSUQgbnVtYmVycyAoc3BlY3RhdG9yIDEgZmlyc3QsIGZvbGxvd2VkIGJ5IHNwZWN0YXRvciAyLCBldGMuKS4gVGhpcyBvcmRlciByZXN1bHRlZCBpbiBzb21lIHNwZWN0YXRvcnMgcmVjZWl2aW5nIGZld2VyIGNob3BzIHRoYW4gdGhleSBpbml0aWFsbHkgdGhvdWdodCB0aGV5IHdvdWxkIGdldC4gVGhlIGZvbGxvd2luZyBpbWFnZSBjb3JyZXNwb25kcyB0byB0aGUgZmlyc3QgZXhhbXBsZSB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcm9sbC5wbmdcIiBzdHlsZT1cImhlaWdodDo2N3B4OyB3aWR0aDozMTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHdoaWNoIHNwZWN0YXRvciBleHBlY3RlZCB0byBnZXQgdGhlIG1vc3Qgd2FsbnV0IHJvbGwgY2hvcHMsIGFuZCB3aGljaCBzcGVjdGF0b3IgYWN0dWFsbHkgZ290IHRoZSBtb3N0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTCAoMSAmbGU7IEwgJmxlOyAxMDAwKSwgdGhlIGxlbmd0aCBvZiB0aGUgd2FsbnV0IHJvbGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDApLCB0aGUgbnVtYmVyIG9mIHNwZWN0YXRvcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBQPHN1Yj5pPFwvc3ViPiBhbmQgSzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IEs8c3ViPmk8XC9zdWI+ICZsZTsgTCwgaSA9IDEuLk4pLCB0aGUgdmFsdWVzIFAgYW5kIEsgYXMgZGVzY3JpYmVkIGluIHRoZSBwcm9ibGVtIHN0YXRlbWVudCBmb3Igc3BlY3RhdG9yIG51bWJlciBpLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIElEIG51bWJlciBvZiB0aGUgc3BlY3RhdG9yIHdobyB3YXMgZXhwZWN0aW5nIHRvIHJlY2VpdmUgdGhlIG1vc3Qgd2FsbnV0IHJvbGwgY2hvcHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBJRCBudW1iZXIgb2YgdGhlIHNwZWN0YXRvciB3aG8gYWN0dWFsbHkgcmVjZWl2ZWQgdGhlIG1vc3Qgd2FsbnV0IHJvbGwgY2hvcHMgaW4gdGhlIGVuZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gYm90aCBjYXNlcywgaWYgdGhlcmUgaXMgbW9yZSB0aGFuIG9uZSBzcGVjdGF0b3Igc2F0aXNmeWluZyB0aGUgY29uZGl0aW9uLCBvdXRwdXQgdGhlIG9uZSB3aXRoIHRoZSBzbWFsbGVzdCBJRC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #4 1번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: djm03178