시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 964 35 27 22.689%

문제

네버랜드는 한국에서 가장 큰 규모를 자랑하는 동물원이다. 이번에 이 동물원은 야생 상태와 흡사한 생태 단지를 만들기 위해서 근처 부지를 구입했다.

동물원에서 가장 인기있는 동물은 원숭이이다. 원숭이는 점프하고 나무를 기어 오르는 것과 같은 기술을 이용해서 남녀노소 모든 방문객을 즐겁게 해준다.

원숭이는 크게 두 종으로 나눌 수 있다. 한 종은 나무를 오르고, 코코넛을 따는 것에 특화되어 있는 종이고, 다른 종은 코코넛을 여는데 특화되어있다.

첫 번째 원숭이 종은 총 N마리, 두 번째는 M마리가 있다. 각각의 종은 번호가 1부터 차례대로 매겨져 있다.

첫 번째 종의 원숭이 중 k번째 원숭이는 오를 나무를 찾아 첫 코코넛을 따는데 Ak초가 걸린다. 이후에 Bk초마다 새로운 코코넛을 생산한다.

두 번째 종의 원숭이 중 k번째 원숭이는 코코넛을 여는 좋은 도구를 찾고, 첫 코코넛을 여는데 Ck초가 걸린다. 이후 Dk초마다 새로운 코코넛을 열 수 있다.

안타깝게도, 두 원숭이 종은 서로 사이가 좋지 않기 때문에 동시에 같은 장소에 있을 수 없다. 따라서, 동물원 사육사는 첫 번째 원숭이 종이 코코넛을 모두 따면 즉시 우리로 돌려 보내고 두 번째 종을 부를 것이다.

동물원 사육사는 첫 번째 종이 모든 코코넛을 따는 즉시 도착한다. 우리로 보내는 시간과 우리에서 원숭이를 불러오는 시간은 무시할 수 있을 만큼 매우 작다.

상근이는 두 번째 종을 매우 좋아한다. 하지만, 언제 가야 되는지를 모르고 있다. 원숭이가 생태 단지에 있는 전체 시간이 주어졌을 때, 언제 도착하면 두 번째 원숭이를 볼 수 있는지 구하는 프로그램을 작성하시오. 상근이는 전체 코코넛의 개수를 알 수 없다.

입력

첫째 줄에 원숭이가 생태 부지에 있는 전체 시간 T (1 ≤ T ≤ 1,000,000,000)가 주어진다.

둘째 줄에는 첫 번째 원숭이의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 k번째 원숭이의 정보 Ak와 Bk가 주어진다. (1 ≤ Ak, Bk ≤ 1,000,000,000)

다음 줄에는 두 번째 원숭이의 수 M이 주어진다. (1 ≤ M ≤ 100)

다음 M개 줄에는 k번째 원숭이의 정보 Ck와 Dk가 주어진다. (1 ≤ Ck, Dk, ≤ 1,000,000,000)

출력

첫째 줄에 첫 번째 종이 우리로 들어가는 시간이자 두 번째 종이 생태 단지로 들어오는 시간을 출력한다.

예제 입력 1

12
1
3 1
1
5 1

예제 출력 1

5

힌트

예제의 경우는 코코넛이 세 개 있는 경우다.

첫 번째 종은 한 마리다. 이 원숭이가 나무를 올라서 첫 코코넛을 따는데 걸리는 시간은 3초이다. 그 다음 4초에 두 번째 코코넛을 따며, 5초에 세 번째 코코넛을 딴다.

사육사는 문을 연지 5초가 지났을 때, 생태 단지에 들어와서 첫 원숭이를 우리로 돌려보내고 두 번째 종을 생태 단지로 불러온다. 이 시간부터 두 번째 종을 볼 수 있기 때문에 정답은 5이다.

문을 연 시간부터 10초가 지나면 도구를 찾고 첫 코코넛을 따고, 11초에 두 번째 코코넛, 12초에 세 번째 코코넛을 딴다. 이제 사육사가 들어와서 다시 원숭이를 우리로 돌려 보낸다.

W3sicHJvYmxlbV9pZCI6IjI5NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWJiM2NcdWM2ZDAgXHVkNjU1XHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxMjRcdWJjODRcdWI3OWNcdWI0ZGNcdWIyOTQgXHVkNTVjXHVhZDZkXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhZGRjXHViYWE4XHViOTdjIFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YjI5NCBcdWIzZDlcdWJiM2NcdWM2ZDBcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWM3NzQgXHViM2Q5XHViYjNjXHVjNmQwXHVjNzQwIFx1YzU3Y1x1YzBkZCBcdWMwYzFcdWQwZGNcdWM2NDAgXHVkNzYxXHVjMGFjXHVkNTVjIFx1YzBkZFx1ZDBkYyBcdWIyZThcdWM5YzBcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFkZmNcdWNjOTggXHViZDgwXHVjOWMwXHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHViYjNjXHVjNmQwXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3NzhcdWFlMzBcdWM3ODhcdWIyOTQgXHViM2Q5XHViYjNjXHVjNzQwIFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHVjNmQwXHVjMjJkXHVjNzc0XHViMjk0IFx1YzgxMFx1ZDUwNFx1ZDU1OFx1YWNlMCBcdWIwOThcdWJiMzRcdWI5N2MgXHVhZTMwXHVjNWI0IFx1YzYyNFx1Yjk3NFx1YjI5NCBcdWFjODNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWUzMFx1YzIyMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViMGE4XHViMTQwXHViMTc4XHVjMThjIFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJiMzhcdWFjMWRcdWM3NDQgXHVjOTkwXHVhYzgxXHVhYzhjIFx1ZDU3NFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmQwXHVjMjJkXHVjNzc0XHViMjk0IFx1ZDA2Y1x1YWM4YyBcdWI0NTAgXHVjODg1XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NWMgXHVjODg1XHVjNzQwIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWM2MjRcdWI5NzRcdWFjZTAsIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzBcdWIyOTQgXHVhYzgzXHVjNWQwIFx1ZDJiOVx1ZDY1NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjODg1XHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVjODg1XHVjNzQwIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWM1ZWNcdWIyOTRcdWIzNzAgXHVkMmI5XHVkNjU0XHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzZkMFx1YzIyZFx1Yzc3NCBcdWM4ODVcdWM3NDAgXHVjZDFkIE5cdWI5YzhcdWI5YWMsIFx1YjQ1MCBcdWJjODhcdWM5ZjhcdWIyOTQgTVx1YjljOFx1YjlhY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4ODVcdWM3NDAgXHViYzg4XHVkNjM4XHVhYzAwIDFcdWJkODBcdWQxMzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzU4IFx1YzZkMFx1YzIyZFx1Yzc3NCBcdWM5MTEga1x1YmM4OFx1YzlmOCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWIyOTQgXHVjNjI0XHViOTdjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWNjM2VcdWM1NDQgXHVjY2FiIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzBcdWIyOTRcdWIzNzAgQTxzdWI+azxcL3N1Yj5cdWNkMDhcdWFjMDAgXHVhYzc4XHViOWIwXHViMmU0LiBcdWM3NzRcdWQ2YzRcdWM1ZDAgQjxzdWI+azxcL3N1Yj5cdWNkMDhcdWI5YzhcdWIyZTQgXHVjMGM4XHViODVjXHVjNmI0IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWMwZGRcdWMwYjBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzU4IFx1YzZkMFx1YzIyZFx1Yzc3NCBcdWM5MTEga1x1YmM4OFx1YzlmOCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWIyOTQgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YzVlY1x1YjI5NCBcdWM4OGJcdWM3NDAgXHViM2M0XHVhZDZjXHViOTdjIFx1Y2MzZVx1YWNlMCwgXHVjY2FiIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWM1ZWNcdWIyOTRcdWIzNzAgQzxzdWI+azxcL3N1Yj5cdWNkMDhcdWFjMDAgXHVhYzc4XHViOWIwXHViMmU0LiBcdWM3NzRcdWQ2YzQgRDxzdWI+azxcL3N1Yj5cdWNkMDhcdWI5YzhcdWIyZTQgXHVjMGM4XHViODVjXHVjNmI0IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWM1ZjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ4XHVkMGMwXHVhZTVkXHVhYzhjXHViM2M0LCBcdWI0NTAgXHVjNmQwXHVjMjJkXHVjNzc0IFx1Yzg4NVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHVjMGFjXHVjNzc0XHVhYzAwIFx1Yzg4Ylx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWFjMTlcdWM3NDAgXHVjN2E1XHVjMThjXHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjNkOVx1YmIzY1x1YzZkMCBcdWMwYWNcdWM3MjFcdWMwYWNcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM2ZDBcdWMyMmRcdWM3NzQgXHVjODg1XHVjNzc0IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWJhYThcdWI0NTAgXHViNTMwXHViYTc0IFx1Yzk4OVx1YzJkYyBcdWM2YjBcdWI5YWNcdWI4NWMgXHViM2NjXHViODI0IFx1YmNmNFx1YjBiNFx1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc0NCBcdWJkODBcdWI5N2MgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWJiM2NcdWM2ZDAgXHVjMGFjXHVjNzIxXHVjMGFjXHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzc0IFx1YmFhOFx1YjRlMCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViNTMwXHViMjk0IFx1Yzk4OVx1YzJkYyBcdWIzYzRcdWNjMjlcdWQ1NWNcdWIyZTQuIFx1YzZiMFx1YjlhY1x1Yjg1YyBcdWJjZjRcdWIwYjRcdWIyOTQgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YzZiMFx1YjlhY1x1YzVkMFx1YzExYyBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI5N2MgXHViZDg4XHViN2VjXHVjNjI0XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJiMzRcdWMyZGNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI5Y2NcdWQwN2MgXHViOWU0XHVjNmIwIFx1Yzc5MVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzQ0IFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNWI4XHVjODFjIFx1YWMwMFx1YzU3YyBcdWI0MThcdWIyOTRcdWM5YzBcdWI5N2MgXHViYWE4XHViOTc0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzBkZFx1ZDBkYyBcdWIyZThcdWM5YzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgwNFx1Y2NiNCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWI4XHVjODFjIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YmE3NCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yjk3YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzgwNFx1Y2NiNCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzU0YyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHVjMGRkXHVkMGRjIFx1YmQ4MFx1YzljMFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODA0XHVjY2I0IFx1YzJkY1x1YWMwNCBUICgxICZsZTsgVCAmbGU7IDEsMDAwLDAwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IGtcdWJjODhcdWM5ZjggXHVjNmQwXHVjMjJkXHVjNzc0XHVjNzU4IFx1YzgxNVx1YmNmNCBBPHN1Yj5rPFwvc3ViPlx1YzY0MCBCPHN1Yj5rPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQTxzdWI+azxcL3N1Yj4sIEI8c3ViPms8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IGtcdWJjODhcdWM5ZjggXHVjNmQwXHVjMjJkXHVjNzc0XHVjNzU4IFx1YzgxNVx1YmNmNCBDPHN1Yj5rPFwvc3ViPlx1YzY0MCBEPHN1Yj5rPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQzxzdWI+azxcL3N1Yj4sIEQ8c3ViPms8XC9zdWI+LCAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NCBcdWM2YjBcdWI5YWNcdWI4NWMgXHViNGU0XHVjNWI0XHVhYzAwXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1Yzc5MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NCBcdWMwZGRcdWQwZGMgXHViMmU4XHVjOWMwXHViODVjIFx1YjRlNFx1YzViNFx1YzYyNFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHViMjk0IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc3NCBcdWMxMzggXHVhYzFjIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzQwIFx1ZDU1YyBcdWI5YzhcdWI5YWNcdWIyZTQuIFx1Yzc3NCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWFjMDAgXHViMDk4XHViYjM0XHViOTdjIFx1YzYyY1x1Yjc3Y1x1YzExYyBcdWNjYWIgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjUzMFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIDNcdWNkMDhcdWM3NzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgNFx1Y2QwOFx1YzVkMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzBcdWJhNzAsIDVcdWNkMDhcdWM1ZDAgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViNTM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWM3MjFcdWMwYWNcdWIyOTQgXHViYjM4XHVjNzQ0IFx1YzVmMFx1YzljMCA1XHVjZDA4XHVhYzAwIFx1YzljMFx1YjBhY1x1Yzc0NCBcdWI1NGMsIFx1YzBkZFx1ZDBkYyBcdWIyZThcdWM5YzBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNjQwXHVjMTFjIFx1Y2NhYiBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI5N2MgXHVjNmIwXHViOWFjXHViODVjIFx1YjNjY1x1YjgyNFx1YmNmNFx1YjBiNFx1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc0NCBcdWMwZGRcdWQwZGMgXHViMmU4XHVjOWMwXHViODVjIFx1YmQ4OFx1YjdlY1x1YzYyOFx1YjJlNC4gXHVjNzc0IFx1YzJkY1x1YWMwNFx1YmQ4MFx1ZDEzMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc0NCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjODE1XHViMmY1XHVjNzQwIDVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc0NCBcdWM1ZjAgXHVjMmRjXHVhYzA0XHViZDgwXHVkMTMwIDEwXHVjZDA4XHVhYzAwIFx1YzljMFx1YjA5OFx1YmE3NCBcdWIzYzRcdWFkNmNcdWI5N2MgXHVjYzNlXHVhY2UwIFx1Y2NhYiBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViNTMwXHVhY2UwLCAxMVx1Y2QwOFx1YzVkMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Y2Y1NFx1Y2Y1NFx1YjExYiwgMTJcdWNkMDhcdWM1ZDAgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViNTM0XHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjMGFjXHVjNzIxXHVjMGFjXHVhYzAwIFx1YjRlNFx1YzViNFx1YzY0MFx1YzExYyBcdWIyZTRcdWMyZGMgXHVjNmQwXHVjMjJkXHVjNzc0XHViOTdjIFx1YzZiMFx1YjlhY1x1Yjg1YyBcdWIzY2NcdWI4MjQgXHViY2Y0XHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjk2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNWQURBIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbG9jYWwgem9vIGhhcyBhY3F1aXJlZCBhIGxhcmdlIG9wZW4gZ2FyZGVuIGluIHdoaWNoIGFuaW1hbHMgbWF5IGZyZWVseSBtb3ZlIGFzIGluIHRoZWlyIG5hdHVyYWwgaGFiaXRhdHMgYW5kIGVudGVydGFpbiB2aXNpdG9ycyB3aXRoIHRoZWlyIHVzdWFsIHNoZW5hbmlnYW5zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbW9zdCBwb3B1bGFyIGFuaW1hbHMgYXJlIG1vbmtleXMuIFdpdGggdGhlaXIgY2xpbWJpbmcgYW5kIGp1bXBpbmcgYW5kIG90aGVyIHNraWxscywgdGhleSBkZWxpZ2h0IG9sZCBhbmQgeW91bmcgdmlzaXRvcnMgYWxpa2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uZSBzcGVjaWVzIG9mIG1vbmtleSBoYXMgc3BlY2lhbGl6ZWQgaW4gY2xpbWJpbmcgdGFsbCB0cmVlcyBhbmQgcGlja2luZyBvZmYgY29jb251dHMuIEFub3RoZXIgc3BlY2llcyBoYXMgc3BlY2lhbGl6ZWQgaW4gYnJlYWtpbmcgdGhlbSBvcGVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVyZSBhcmUgTiBtb25rZXlzIG9mIHRoZSBmaXJzdCB0eXBlIChudW1iZXJlZCAxIHRocm91Z2ggTikgYW5kIE0gbW9ua2V5cyBvZiB0aGUgc2Vjb25kIHR5cGUgKG51bWJlcmVkIDEgdGhyb3VnaCBNKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TW9ua2V5IGsgb2YgdGhlIGZpcnN0IHR5cGUgdGFrZXMgQTxzdWI+azxcL3N1Yj4gc2Vjb25kcyB0byBmaW5kIGEgZ29vZCBzcG90IG9uIHRoZSB0cmVlLCBhZnRlciB3aGljaCBpdCBwaWNrcyBvZmYgaXRzIGZpcnN0IGNvY29udXQuIEFmdGVyIHRoYXQgdGhlIG1vbmtleSBwcm9kdWNlcyBhIG5ldyBjb2NvbnV0IGV2ZXJ5IEI8c3ViPms8XC9zdWI+IHNlY29uZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1vbmtleSBrIG9mIHRoZSBzZWNvbmQgdHlwZSB0YWtlcyBDPHN1Yj5rPFwvc3ViPiBzZWNvbmRzIHRvIGZpbmQgYSBnb29kIHRvb2wgZm9yIG9wZW5pbmcgdGhlIGNvY29udXRzLCBhZnRlciB3aGljaCBpdCBvcGVucyBpdHMgZmlyc3QgY29jb251dC4gQWZ0ZXIgdGhhdCB0aGUgbW9ua2V5IG9wZW5zIGFub3RoZXIgY29jb251dCBldmVyeSBEPHN1Yj5rPFwvc3ViPiBzZWNvbmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCB0aGUgc2Vjb25kIHR5cGUgb2YgbW9ua2V5IGlzIGV4dHJlbWVseSBhZ2dyZXNzaXZlIHNvIHRoZSB0d28gdHlwZXMgbWF5IG5vdCBiZSBpbiB0aGUgZ2FyZGVuIGF0IHRoZSBzYW1lIHRpbWUuIFRoZXJlZm9yZSwgem9vIGtlZXBlcnMgd2lsbCBjaGFzZSBhd2F5IHRoZSBmaXJzdCB0eXBlIG9mIG1vbmtleXMgYXMgc29vbiBhcyB0aGV5IGhhdmUgcGlja2VkIG9mZiBhbGwgdGhlIGNvY29udXRzLiBTaW1pbGFybHksIGlmIG1vbmtleXMgb2YgdGhlIHNhbWUgdHlwZSBzdGF5IHRvbyBsb25nIGFmdGVyIG9wZW5pbmcgYWxsIHRoZSBjb2NvbnV0cywgZmlnaHRzIHdpbGwgZW5zdWUuIEJlY2F1c2Ugb2YgdGhhdCwgem9vIGtlZXBlcnMgd2lsbCBzZW5kIHRoZW0gYXdheSBhcyBzb29uIGFzIHRoZXkgaGF2ZSBvcGVuZWQgYWxsIHRoZSBjb2NvbnV0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHpvbyBrZWVwZXJzIGZpcnN0IGFycml2ZSBpbW1lZGlhdGVseSBhZnRlciBhbGwgY29jb251dHMgaGF2ZSBiZWVuIHBpY2tlZCwgYW5kIGFnYWluIGltbWVkaWF0ZWx5IGFmdGVyIHRoZSBtb25rZXlzIG9wZW4gdGhlbSBhbGwuIFRoZSB0aW1lIG5lZWRlZCBmb3IgbW9ua2V5cyB0byBlbnRlciBvciBsZWF2ZSB0aGUgZ2FyZGVuIGlzIGFsc28gbmVnbGlnaWJseSBzbWFsbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG9taXNsYXYgZXNwZWNpYWxseSBsaWtlcyB0aGUgc2Vjb25kIHR5cGUgb2YgbW9ua2V5LCBidXQgY2FuIG5ldmVyIGd1ZXNzIHdoZW4gdG8gYXJyaXZlIGluIG9yZGVyIHRvIHNlZSB0aGVtLiBIZWxwIGhpbSBjYWxjdWxhdGUgdGhlIHRpbWUgd2hlbiB0aGUgc2Vjb25kIHR5cGUgYXJyaXZlcyBpZiBoZSBrbm93cyB0aGUgdG90YWwgdGltZSB0aGF0IG1vbmtleXMgc3BlbnQgaW4gdGhlIGdhcmRlbiwgYnV0IGRvZXMgbm90IGtub3cgdGhlIG51bWJlciBvZiBjb2NvbnV0cyBpbiB0aGUgZ2FyZGVuLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgVCAoMSAmbGU7IFQgJmxlOyAxIDAwMCAwMDAgMDAwKSwgdGhlIHRvdGFsIHRpbWUgdGhhdCBtb25rZXlzIHNwZW50IGluIHRoZSBnYXJkZW4sIGluIHNlY29uZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIG1vbmtleXMgb2YgdGhlIGZpcnN0IHR5cGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBBPHN1Yj5rPFwvc3ViPiBhbmQgQjxzdWI+azxcL3N1Yj4gKDEgJmxlOyBBPHN1Yj5rPFwvc3ViPiwgQjxzdWI+azxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwKSwgaG93IGZhc3QgbW9ua2V5IGsgb2YgdGhlIGZpcnN0IHR5cGUgaXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXIgTSAoMSAmbGU7IE0gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIG1vbmtleXMgb2YgdGhlIHNlY29uZCB0eXBlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgQzxzdWI+azxcL3N1Yj4gYW5kIEQ8c3ViPms8XC9zdWI+ICgxICZsZTsgQzxzdWI+azxcL3N1Yj4sIEQ8c3ViPms8XC9zdWI+ICZsZTsgMSAwMDAgMDAwIDAwMCksIGhvdyBmYXN0IG1vbmtleSBrIG9mIHRoZSBzZWNvbmQgdHlwZSBpcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBzZWNvbmRzIGJldHdlZW4gdGhlIGFycml2YWwgb2YgdGhlIGZpcnN0IHR5cGUgb2YgbW9ua2V5cyBhbmQgdGhlIGFycml2YWwgb2YgdGhlIHNlY29uZCB0eXBlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZXhhbXBsZSwgaXQgdHVybnMgb3V0IHRoZXJlIGFyZSB0aHJlZSBjb2NvbnV0cyBpbiB0aGUgZ2FyZGVuOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBtb25rZXkgb2YgdGhlIGZpcnN0IHR5cGUgcGlja3Mgb2ZmIHRoZSBmaXJzdCBjb2NvbnV0IDMgc2Vjb25kcyBhZnRlciB0aGUgZ2FyZGVuIHdhcyBvcGVuZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBtb25rZXkgcGlja3Mgb2ZmIHRoZSBzZWNvbmQgY29jb251dCA0IHNlY29uZHMgYWZ0ZXIgdGhlIGdhcmRlbiBpcyBvcGVuZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBtb25rZXkgcGlja3Mgb2ZmIHRoZSB0aGlyZCBjb2NvbnV0IDUgc2Vjb25kcyBhZnRlciB0aGUgZ2FyZGVuIGlzIG9wZW5lZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Wm9vIGtlZXBlcnMgY29tZSBpbiBhbmQgZXNjb3J0IHRoZSBtb25rZXkgb3V0LiBUaGUgbW9ua2V5IG9mIHRoZSBzZWNvbmQgdHlwZSBhcnJpdmVzLiBUaGUgb3V0cHV0IGlzIDUgYmVjYXVzZSB0aGlzIGlzIHdoZW4gVG9taXNsYXYgd2FudHMgdG8gYXJyaXZlLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbW9ua2V5IG9mIHRoZSBzZWNvbmQgdHlwZSBvcGVucyB0aGUgZmlyc3QgY29jb251dCAxMCBzZWNvbmRzIGFmdGVyIHRoZSBnYXJkZW4gd2FzIG9wZW5lZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIG1vbmtleSBvcGVucyB0aGUgc2Vjb25kIGNvY29udXQgMTEgc2Vjb25kcyBhZnRlciB0aGUgZ2FyZGVuIHdhcyBvcGVuZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBtb25rZXkgb3BlbnMgdGhlIHRoaXJkIGNvY29udXQgMTIgc2Vjb25kcyBhZnRlciB0aGUgZ2FyZGVuIHdhcyBvcGVuZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlpvbyBrZWVwZXJzIGNvbWUgaW4gYW5kIGVzY29ydCB0aGUgbW9ua2V5IG91dC4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #2 4번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: doju
  • 문제의 오타를 찾은 사람: jh05013