시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB1039413320.886%

문제

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

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

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

첫 번째 원숭이 종은 총 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

예제 입력 2

20
2
3 2
1 3
3
3 1
4 1
5 1

예제 출력 2

13

힌트

첫 번째 예제는 코코넛이 세 개 있는 경우다.

첫 번째 종은 한 마리다. 이 원숭이가 나무를 올라서 첫 코코넛을 따는데 걸리는 시간은 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+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1YjI5NCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NzQgXHVjMTM4IFx1YWMxYyBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc0MCBcdWQ1NWMgXHViOWM4XHViOWFjXHViMmU0LiBcdWM3NzQgXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWM2MmNcdWI3N2NcdWMxMWMgXHVjY2FiIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzBcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAzXHVjZDA4XHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIDRcdWNkMDhcdWM1ZDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViNTMwXHViYTcwLCA1XHVjZDA4XHVjNWQwIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjUzNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVjNzIxXHVjMGFjXHViMjk0IFx1YmIzOFx1Yzc0NCBcdWM1ZjBcdWM5YzAgNVx1Y2QwOFx1YWMwMCBcdWM5YzBcdWIwYWNcdWM3NDQgXHViNTRjLCBcdWMwZGRcdWQwZGMgXHViMmU4XHVjOWMwXHVjNWQwIFx1YjRlNFx1YzViNFx1YzY0MFx1YzExYyBcdWNjYWIgXHVjNmQwXHVjMjJkXHVjNzc0XHViOTdjIFx1YzZiMFx1YjlhY1x1Yjg1YyBcdWIzY2NcdWI4MjRcdWJjZjRcdWIwYjRcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NDQgXHVjMGRkXHVkMGRjIFx1YjJlOFx1YzljMFx1Yjg1YyBcdWJkODhcdWI3ZWNcdWM2MjhcdWIyZTQuIFx1Yzc3NCBcdWMyZGNcdWFjMDRcdWJkODBcdWQxMzAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NDQgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc0MCA1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3NDQgXHVjNWYwIFx1YzJkY1x1YWMwNFx1YmQ4MFx1ZDEzMCAxMFx1Y2QwOFx1YWMwMCBcdWM5YzBcdWIwOThcdWJhNzQgXHViM2M0XHVhZDZjXHViOTdjIFx1Y2MzZVx1YWNlMCBcdWNjYWIgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjUzMFx1YWNlMCwgMTFcdWNkMDhcdWM1ZDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWNmNTRcdWNmNTRcdWIxMWIsIDEyXHVjZDA4XHVjNWQwIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjUzNFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YzBhY1x1YzcyMVx1YzBhY1x1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2NDBcdWMxMWMgXHViMmU0XHVjMmRjIFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yjk3YyBcdWM2YjBcdWI5YWNcdWI4NWMgXHViM2NjXHViODI0IFx1YmNmNFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5NjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTVkFEQSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGxvY2FsIHpvbyBoYXMgYWNxdWlyZWQgYSBsYXJnZSBvcGVuIGdhcmRlbiBpbiB3aGljaCBhbmltYWxzIG1heSBmcmVlbHkgbW92ZSBhcyBpbiB0aGVpciBuYXR1cmFsIGhhYml0YXRzIGFuZCBlbnRlcnRhaW4gdmlzaXRvcnMgd2l0aCB0aGVpciB1c3VhbCBzaGVuYW5pZ2Fucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG1vc3QgcG9wdWxhciBhbmltYWxzIGFyZSBtb25rZXlzLiBXaXRoIHRoZWlyIGNsaW1iaW5nIGFuZCBqdW1waW5nIGFuZCBvdGhlciBza2lsbHMsIHRoZXkgZGVsaWdodCBvbGQgYW5kIHlvdW5nIHZpc2l0b3JzIGFsaWtlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbmUgc3BlY2llcyBvZiBtb25rZXkgaGFzIHNwZWNpYWxpemVkIGluIGNsaW1iaW5nIHRhbGwgdHJlZXMgYW5kIHBpY2tpbmcgb2ZmIGNvY29udXRzLiBBbm90aGVyIHNwZWNpZXMgaGFzIHNwZWNpYWxpemVkIGluIGJyZWFraW5nIHRoZW0gb3Blbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIE4gbW9ua2V5cyBvZiB0aGUgZmlyc3QgdHlwZSAobnVtYmVyZWQgMSB0aHJvdWdoIE4pIGFuZCBNIG1vbmtleXMgb2YgdGhlIHNlY29uZCB0eXBlIChudW1iZXJlZCAxIHRocm91Z2ggTSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1vbmtleSBrIG9mIHRoZSBmaXJzdCB0eXBlIHRha2VzIEE8c3ViPms8XC9zdWI+IHNlY29uZHMgdG8gZmluZCBhIGdvb2Qgc3BvdCBvbiB0aGUgdHJlZSwgYWZ0ZXIgd2hpY2ggaXQgcGlja3Mgb2ZmIGl0cyBmaXJzdCBjb2NvbnV0LiBBZnRlciB0aGF0IHRoZSBtb25rZXkgcHJvZHVjZXMgYSBuZXcgY29jb251dCBldmVyeSBCPHN1Yj5rPFwvc3ViPiBzZWNvbmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Nb25rZXkgayBvZiB0aGUgc2Vjb25kIHR5cGUgdGFrZXMgQzxzdWI+azxcL3N1Yj4gc2Vjb25kcyB0byBmaW5kIGEgZ29vZCB0b29sIGZvciBvcGVuaW5nIHRoZSBjb2NvbnV0cywgYWZ0ZXIgd2hpY2ggaXQgb3BlbnMgaXRzIGZpcnN0IGNvY29udXQuIEFmdGVyIHRoYXQgdGhlIG1vbmtleSBvcGVucyBhbm90aGVyIGNvY29udXQgZXZlcnkgRDxzdWI+azxcL3N1Yj4gc2Vjb25kcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgdGhlIHNlY29uZCB0eXBlIG9mIG1vbmtleSBpcyBleHRyZW1lbHkgYWdncmVzc2l2ZSBzbyB0aGUgdHdvIHR5cGVzIG1heSBub3QgYmUgaW4gdGhlIGdhcmRlbiBhdCB0aGUgc2FtZSB0aW1lLiBUaGVyZWZvcmUsIHpvbyBrZWVwZXJzIHdpbGwgY2hhc2UgYXdheSB0aGUgZmlyc3QgdHlwZSBvZiBtb25rZXlzIGFzIHNvb24gYXMgdGhleSBoYXZlIHBpY2tlZCBvZmYgYWxsIHRoZSBjb2NvbnV0cy4gU2ltaWxhcmx5LCBpZiBtb25rZXlzIG9mIHRoZSBzYW1lIHR5cGUgc3RheSB0b28gbG9uZyBhZnRlciBvcGVuaW5nIGFsbCB0aGUgY29jb251dHMsIGZpZ2h0cyB3aWxsIGVuc3VlLiBCZWNhdXNlIG9mIHRoYXQsIHpvbyBrZWVwZXJzIHdpbGwgc2VuZCB0aGVtIGF3YXkgYXMgc29vbiBhcyB0aGV5IGhhdmUgb3BlbmVkIGFsbCB0aGUgY29jb251dHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB6b28ga2VlcGVycyBmaXJzdCBhcnJpdmUgaW1tZWRpYXRlbHkgYWZ0ZXIgYWxsIGNvY29udXRzIGhhdmUgYmVlbiBwaWNrZWQsIGFuZCBhZ2FpbiBpbW1lZGlhdGVseSBhZnRlciB0aGUgbW9ua2V5cyBvcGVuIHRoZW0gYWxsLiBUaGUgdGltZSBuZWVkZWQgZm9yIG1vbmtleXMgdG8gZW50ZXIgb3IgbGVhdmUgdGhlIGdhcmRlbiBpcyBhbHNvIG5lZ2xpZ2libHkgc21hbGwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRvbWlzbGF2IGVzcGVjaWFsbHkgbGlrZXMgdGhlIHNlY29uZCB0eXBlIG9mIG1vbmtleSwgYnV0IGNhbiBuZXZlciBndWVzcyB3aGVuIHRvIGFycml2ZSBpbiBvcmRlciB0byBzZWUgdGhlbS4gSGVscCBoaW0gY2FsY3VsYXRlIHRoZSB0aW1lIHdoZW4gdGhlIHNlY29uZCB0eXBlIGFycml2ZXMgaWYgaGUga25vd3MgdGhlIHRvdGFsIHRpbWUgdGhhdCBtb25rZXlzIHNwZW50IGluIHRoZSBnYXJkZW4sIGJ1dCBkb2VzIG5vdCBrbm93IHRoZSBudW1iZXIgb2YgY29jb251dHMgaW4gdGhlIGdhcmRlbi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIFQgKDEgJmxlOyBUICZsZTsgMSAwMDAgMDAwIDAwMCksIHRoZSB0b3RhbCB0aW1lIHRoYXQgbW9ua2V5cyBzcGVudCBpbiB0aGUgZ2FyZGVuLCBpbiBzZWNvbmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBtb25rZXlzIG9mIHRoZSBmaXJzdCB0eXBlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgQTxzdWI+azxcL3N1Yj4gYW5kIEI8c3ViPms8XC9zdWI+ICgxICZsZTsgQTxzdWI+azxcL3N1Yj4sIEI8c3ViPms8XC9zdWI+ICZsZTsgMSAwMDAgMDAwIDAwMCksIGhvdyBmYXN0IG1vbmtleSBrIG9mIHRoZSBmaXJzdCB0eXBlIGlzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE0gKDEgJmxlOyBNICZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBtb25rZXlzIG9mIHRoZSBzZWNvbmQgdHlwZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIEM8c3ViPms8XC9zdWI+IGFuZCBEPHN1Yj5rPFwvc3ViPiAoMSAmbGU7IEM8c3ViPms8XC9zdWI+LCBEPHN1Yj5rPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDApLCBob3cgZmFzdCBtb25rZXkgayBvZiB0aGUgc2Vjb25kIHR5cGUgaXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2Ygc2Vjb25kcyBiZXR3ZWVuIHRoZSBhcnJpdmFsIG9mIHRoZSBmaXJzdCB0eXBlIG9mIG1vbmtleXMgYW5kIHRoZSBhcnJpdmFsIG9mIHRoZSBzZWNvbmQgdHlwZS48XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGV4YW1wbGUsIGl0IHR1cm5zIG91dCB0aGVyZSBhcmUgdGhyZWUgY29jb251dHMgaW4gdGhlIGdhcmRlbjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgbW9ua2V5IG9mIHRoZSBmaXJzdCB0eXBlIHBpY2tzIG9mZiB0aGUgZmlyc3QgY29jb251dCAzIHNlY29uZHMgYWZ0ZXIgdGhlIGdhcmRlbiB3YXMgb3BlbmVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbW9ua2V5IHBpY2tzIG9mZiB0aGUgc2Vjb25kIGNvY29udXQgNCBzZWNvbmRzIGFmdGVyIHRoZSBnYXJkZW4gaXMgb3BlbmVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbW9ua2V5IHBpY2tzIG9mZiB0aGUgdGhpcmQgY29jb251dCA1IHNlY29uZHMgYWZ0ZXIgdGhlIGdhcmRlbiBpcyBvcGVuZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlpvbyBrZWVwZXJzIGNvbWUgaW4gYW5kIGVzY29ydCB0aGUgbW9ua2V5IG91dC4gVGhlIG1vbmtleSBvZiB0aGUgc2Vjb25kIHR5cGUgYXJyaXZlcy4gVGhlIG91dHB1dCBpcyA1IGJlY2F1c2UgdGhpcyBpcyB3aGVuIFRvbWlzbGF2IHdhbnRzIHRvIGFycml2ZS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIG1vbmtleSBvZiB0aGUgc2Vjb25kIHR5cGUgb3BlbnMgdGhlIGZpcnN0IGNvY29udXQgMTAgc2Vjb25kcyBhZnRlciB0aGUgZ2FyZGVuIHdhcyBvcGVuZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBtb25rZXkgb3BlbnMgdGhlIHNlY29uZCBjb2NvbnV0IDExIHNlY29uZHMgYWZ0ZXIgdGhlIGdhcmRlbiB3YXMgb3BlbmVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbW9ua2V5IG9wZW5zIHRoZSB0aGlyZCBjb2NvbnV0IDEyIHNlY29uZHMgYWZ0ZXIgdGhlIGdhcmRlbiB3YXMgb3BlbmVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5ab28ga2VlcGVycyBjb21lIGluIGFuZCBlc2NvcnQgdGhlIG1vbmtleSBvdXQuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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