시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 673 317 286 48.805%

문제

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

첫 번째 에피소드에 출연하는 요리사는 전설의 요리사 김상근이고, 길이 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+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NDAgXHViYTg3IFx1YzJkY1x1YWMwNFx1YjNkOVx1YzU0OCBcdWM5ZDFcdWM5MTFcdWQ1NzRcdWMxMWMgXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YWNlMCwgXHVjNzc0XHVjODFjIFx1YzJhNFx1ZDI5Y1x1YjUxNFx1YzYyNFx1Yzc1OCBcdWJjMjlcdWNjYWRcdWFjMWQgTlx1YmE4NVx1YzVkMFx1YWM4YyBcdWNmMDBcdWM3NzRcdWQwNmNcdWI5N2MgXHViMDk4XHViMjA0XHVjNWI0IFx1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI4NjQgXHVjZjAwXHVjNzc0XHVkMDZjXHViOTdjIFx1ZDNiY1x1Y2NkMFx1YzExYyAxXHViYmY4XHVkMTMwIFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWM3OThcdWI3N2MgXHViMTkzXHVjNTU4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1Yzg3MFx1YWMwMVx1Yzc3NCAxXHViYzg4LCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjODcwXHVhYzAxXHVjNzc0IExcdWJjODggXHVjODcwXHVhYzAxXHVjNzc0XHViMmU0LiBcdWJjMjlcdWNjYWRcdWFjMWRcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViYzI5XHVjY2FkXHVhYzFkXHVjNzQwIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM4MDFcdWM1YjRcdWMxMWMgXHViMGI4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YjQ1MCBcdWMyMmJcdWM3OTAgUFx1YzY0MCBLXHViOTdjIFx1YzgwMVx1YzViNFx1YzExYyBcdWIwYjRcdWJhNzAsIFBcdWJjODggXHVjODcwXHVhYzAxXHViZDgwXHVkMTMwIEtcdWJjODggXHVjODcwXHVhYzAxXHVjNzQ0IFx1YzZkMFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWM5YzRcdWQ1ODlcdWM3OTAgXHVhY2UwXHVjYzNkXHVjNjAxXHVjNzQwIDFcdWJjODggXHViYzI5XHVjY2FkXHVhYzFkXHVjNzU4IFx1Yzg4NVx1Yzc3NFx1YmQ4MFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkM2JjXHVjY2QwXHVjMTFjIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWM4NzBcdWFjMDFcdWM1ZDAgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjODAxXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzRcdWJiZjggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWM4NzBcdWFjMDFcdWM3NDAgXHViYzg4XHVkNjM4XHViOTdjIFx1YzgwMVx1YzljMCBcdWJhYmJcdWQ1NThcdWFjZTAgXHViMTE4XHVjNWI0XHVhYzA0XHViMmU0LiBcdWM3NzRcdWI3ZjAgXHViYzI5XHVjMmRkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJjMjlcdWNjYWRcdWFjMWRcdWM1ZDBcdWFjOGMgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YzhmY1x1YjJlNFx1YmNmNFx1YjJjOCwgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzZkMFx1Yjc5OCBcdWM2ZDBcdWQ1ODhcdWIzNTggXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmMxYlx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YzBkZFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjNjA4XHVjODFjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcm9sbC5wbmdcIiBzdHlsZT1cImhlaWdodDo2N3B4OyB3aWR0aDozMTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Y2YwMFx1Yzc3NFx1ZDA2YyBcdWM4NzBcdWFjMDFcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWFlMzBcdWIzMDBcdWQ1NWMgXHViYzI5XHVjY2FkXHVhYzFkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWMyZTRcdWM4MWNcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWNmMDBcdWM3NzRcdWQwNmMgXHVjODcwXHVhYzAxXHVjNzQ0IFx1YmMxYlx1YjI5NCBcdWJjMjlcdWNjYWRcdWFjMWRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI4NjQgXHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1YWUzOFx1Yzc3NCBMICgxICZsZTsgTCAmbGU7IDEwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMjlcdWNjYWRcdWFjMWRcdWM3NTggXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YmMyOVx1Y2NhZFx1YWMxZCBpXHVhYzAwIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWM1YjRcdWIwYjggXHVjMjJiXHVjNzkwIFBpXHVjNjQwIEs8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBQPHN1Yj5pPFwvc3ViPiAmbGU7IEs8c3ViPmk8XC9zdWI+ICZsZTsgTCwgaSA9IDEuLk4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWJjMWJcdWM3NDQgXHVhYzgzXHVjNzNjXHViODVjIFx1YWUzMFx1YjMwMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIzNTgmbmJzcDtcdWJjMjlcdWNjYWRcdWFjMWRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyZTRcdWM4MWNcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWM4NzBcdWFjMDFcdWM3NDQgXHViYzFiXHVjNzQwIFx1YmMyOVx1Y2NhZFx1YWMxZFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWJjMWJcdWFjNzBcdWIwOTggXHVjNjA4XHVjMGMxXHViNDE4XHViMjk0IFx1YmMyOVx1Y2NhZFx1YWMxZFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHViYTg1XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9SRUhOSkFDQSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlc2UgZGF5cywgdGhlIFRWIHN0dWRpbyBoYXMgc3RhcnRlZCBzaG9vdGluZyBhbm90aGVyIG5ldyBzZWFzb24gb2YgSmFtaWUgT2xpdmVyJiMzOTtzIGNvb2tpbmcgc2hvdy4gVGhpcyBzZWFzb24sIEphbWllIHBsYW5zIHRvIGludHJvZHVjZSB0aGUgZGVsaWdodHMgb2YgQ3JvYXRpYW4gY3Vpc2luZSB0byB0aGUgd29ybGQuIEluIHRoZSBmaXJzdCBlcGlzb2RlLCB0aGUgbWFzdGVyIGNoZWYgaGFzIGJha2VkIGEgd2FsbnV0IHJvbGwgTCBtZXRlcnMgbG9uZywgdGhlIGxvbmdlc3QgZXZlciBiYWtlZCBpbiB0aGlzIHBhcnQgb2YgdGhlIHdvcmxkLiBBZnRlciBob3VycyBvZiBzd2VhdGluZyBhbmQgdG9pbGluZyBpbiB0aGUga2l0Y2hlbiwgaGUgaGFzIGRlY2lkZWQgdG8gcmV3YXJkIGVhY2ggb25lIG9mIGhpcyBOIGZhaXRoZnVsIHNwZWN0YXRvcnMgaW4gdGhlIHN0dWRpby4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGUgaGFzIGNob3BwZWQgdGhlIHdhbG51dCByb2xsIGludG8gb25lIG1ldGVyIGxvbmcgY2hvcHMgYW5kIG1hcmtlZCB0aGVtIHdpdGggbnVtYmVycyBmcm9tIDEgZG8gTCwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBFYWNoIHNwZWN0YXRvciBoYXMgcmVjZWl2ZWQgYSB1bmlxdWUgbnVtYmVyIElEIChhIHBvc2l0aXZlIGludGVnZXIgZnJvbSAxIHRvIE4pLCBhcyB3ZWxsIGFzIGEgcGFwZXIgd2l0aCB0d28gaW50ZWdlcnMsIFAgYW5kIEsuIEVhY2ggc3BlY3RhdG9yIHdhcyB0aGVuIGFsbG93ZWQgdG8gdGFrZSBhbGwgY2hvcHMgZnJvbSB0aGUgUC10aCB0byB0aGUgSy10aCwgaW5jbHVzaXZlLiBTcGVjdGF0b3JzIHdlcmUgYWxsb3dlZCB0byB0YWtlIHRoZWlyIHNoYXJlIGluIG9yZGVyIG9mIHRoZWlyIElEIG51bWJlcnMgKHNwZWN0YXRvciAxIGZpcnN0LCBmb2xsb3dlZCBieSBzcGVjdGF0b3IgMiwgZXRjLikuIFRoaXMgb3JkZXIgcmVzdWx0ZWQgaW4gc29tZSBzcGVjdGF0b3JzIHJlY2VpdmluZyBmZXdlciBjaG9wcyB0aGFuIHRoZXkgaW5pdGlhbGx5IHRob3VnaHQgdGhleSB3b3VsZCBnZXQuIFRoZSBmb2xsb3dpbmcgaW1hZ2UgY29ycmVzcG9uZHMgdG8gdGhlIGZpcnN0IGV4YW1wbGUgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3JvbGwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjdweDsgd2lkdGg6MzE3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSB3aGljaCBzcGVjdGF0b3IgZXhwZWN0ZWQgdG8gZ2V0IHRoZSBtb3N0IHdhbG51dCByb2xsIGNob3BzLCBhbmQgd2hpY2ggc3BlY3RhdG9yIGFjdHVhbGx5IGdvdCB0aGUgbW9zdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIEwgKDEgJmxlOyBMICZsZTsgMTAwMCksIHRoZSBsZW5ndGggb2YgdGhlIHdhbG51dCByb2xsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwKSwgdGhlIG51bWJlciBvZiBzcGVjdGF0b3JzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgUDxzdWI+aTxcL3N1Yj4gYW5kIEs8c3ViPmk8XC9zdWI+ICgxICZsZTsgUDxzdWI+aTxcL3N1Yj4gJmxlOyBLPHN1Yj5pPFwvc3ViPiAmbGU7IEwsIGkgPSAxLi5OKSwgdGhlIHZhbHVlcyBQIGFuZCBLIGFzIGRlc2NyaWJlZCBpbiB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQgZm9yIHNwZWN0YXRvciBudW1iZXIgaS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBJRCBudW1iZXIgb2YgdGhlIHNwZWN0YXRvciB3aG8gd2FzIGV4cGVjdGluZyB0byByZWNlaXZlIHRoZSBtb3N0IHdhbG51dCByb2xsIGNob3BzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgSUQgbnVtYmVyIG9mIHRoZSBzcGVjdGF0b3Igd2hvIGFjdHVhbGx5IHJlY2VpdmVkIHRoZSBtb3N0IHdhbG51dCByb2xsIGNob3BzIGluIHRoZSBlbmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIGJvdGggY2FzZXMsIGlmIHRoZXJlIGlzIG1vcmUgdGhhbiBvbmUgc3BlY3RhdG9yIHNhdGlzZnlpbmcgdGhlIGNvbmRpdGlvbiwgb3V0cHV0IHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlc3QgSUQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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