시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 832 18 15 29.412%

문제

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

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

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

첫 번째 원숭이 종은 총 N마리, 두 번째는 M마리가 있다. 번호는 둘다 모두 1부터 N까지 매겨져 있다.

첫 번째 종의 원숭이 중 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초에 세 번째 코코넛을 딴다. 이제 사육사가 들어와서 다시 원숭이를 우리로 돌려 보낸다.

W3sicHJvYmxlbV9pZCI6IjI5NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzZDlcdWJiM2NcdWM2ZDAgXHVkNjU1XHVjN2E1IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIxMjRcdWJjODRcdWI3OWNcdWI0ZGNcdWIyOTQgXHVkNTVjXHVhZDZkXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhZGRjXHViYWE4XHViOTdjIFx1Yzc5MFx1Yjc5MVx1ZDU1OFx1YjI5NCBcdWIzZDlcdWJiM2NcdWM2ZDBcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWM3NzQgXHViM2Q5XHViYjNjXHVjNmQwXHVjNzQwIFx1YzU3Y1x1YzBkZCBcdWMwYzFcdWQwZGNcdWM2NDAgXHVkNzYxXHVjMGFjXHVkNTVjIFx1YzBkZFx1ZDBkYyBcdWIyZThcdWM5YzBcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFkZmNcdWNjOTggXHViZDgwXHVjOWMwXHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViM2Q5XHViYjNjXHVjNmQwXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3NzhcdWFlMzBcdWM3ODhcdWIyOTQgXHViM2Q5XHViYjNjXHVjNzQwIFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHVjNmQwXHVjMjJkXHVjNzc0XHViMjk0IFx1YzgxMFx1ZDUwNFx1ZDU1OFx1YWNlMCBcdWIwOThcdWJiMzRcdWI5N2MgXHVhZTMwXHVjNWI0IFx1YzYyNFx1Yjk3NFx1YjI5NCBcdWFjODNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWUzMFx1YzIyMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViMGE4XHViMTQwXHViMTc4XHVjMThjIFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJiMzhcdWFjMWRcdWM3NDQgXHVjOTkwXHVhYzgxXHVhYzhjIFx1ZDU3NFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNmQwXHVjMjJkXHVjNzc0XHViMjk0IFx1ZDA2Y1x1YWM4YyBcdWI0NTAgXHVjODg1XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NWMgXHVjODg1XHVjNzQwIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWM2MjRcdWI5NzRcdWFjZTAsIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzBcdWIyOTQgXHVhYzgzXHVjNWQwIFx1ZDJiOVx1ZDY1NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjODg1XHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVjODg1XHVjNzQwIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWM1ZWNcdWIyOTRcdWIzNzAgXHVkMmI5XHVkNjU0XHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzZkMFx1YzIyZFx1Yzc3NCBcdWM4ODVcdWM3NDAgXHVjZDFkIE5cdWI5YzhcdWI5YWMsIFx1YjQ1MCBcdWJjODhcdWM5ZjhcdWIyOTQgTVx1YjljOFx1YjlhY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWI0NThcdWIyZTQgXHViYWE4XHViNDUwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc1OCBcdWM2ZDBcdWMyMmRcdWM3NzQgXHVjOTExIGtcdWJjODhcdWM5ZjggXHVjNmQwXHVjMjJkXHVjNzc0XHViMjk0IFx1YzYyNFx1Yjk3YyBcdWIwOThcdWJiMzRcdWI5N2MgXHVjYzNlXHVjNTQ0IFx1Y2NhYiBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViNTMwXHViMjk0XHViMzcwIEE8c3ViPms8XC9zdWI+XHVjZDA4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC4gXHVjNzc0XHVkNmM0XHVjNWQwIEI8c3ViPms8XC9zdWI+XHVjZDA4XHViOWM4XHViMmU0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHVjMGRkXHVjMGIwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc1OCBcdWM2ZDBcdWMyMmRcdWM3NzQgXHVjOTExIGtcdWJjODhcdWM5ZjggXHVjNmQwXHVjMjJkXHVjNzc0XHViMjk0IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWM1ZWNcdWIyOTQgXHVjODhiXHVjNzQwIFx1YjNjNFx1YWQ2Y1x1Yjk3YyBcdWNjM2VcdWFjZTAsIFx1Y2NhYiBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHVjNWVjXHViMjk0XHViMzcwIEM8c3ViPms8XC9zdWI+XHVjZDA4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC4gXHVjNzc0XHVkNmM0IEQ8c3ViPms8XC9zdWI+XHVjZDA4XHViOWM4XHViMmU0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHVjNWY0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0OFx1ZDBjMFx1YWU1ZFx1YWM4Y1x1YjNjNCwgXHViNDUwIFx1YzZkMFx1YzIyZFx1Yzc3NCBcdWM4ODVcdWM3NDAgXHVjMTFjXHViODVjIFx1YzBhY1x1Yzc3NFx1YWMwMCBcdWM4OGJcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzE5XHVjNzQwIFx1YzdhNVx1YzE4Y1x1YzVkMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWIzZDlcdWJiM2NcdWM2ZDAgXHVjMGFjXHVjNzIxXHVjMGFjXHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNmQwXHVjMjJkXHVjNzc0IFx1Yzg4NVx1Yzc3NCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViYWE4XHViNDUwIFx1YjUzMFx1YmE3NCBcdWM5ODlcdWMyZGMgXHVjNmIwXHViOWFjXHViODVjIFx1YjNjY1x1YjgyNCBcdWJjZjRcdWIwYjRcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NDQgXHViZDgwXHViOTdjIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViM2Q5XHViYjNjXHVjNmQwIFx1YzBhY1x1YzcyMVx1YzBhY1x1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc3NCBcdWJhYThcdWI0ZTAgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjUzMFx1YjI5NCBcdWM5ODlcdWMyZGMgXHViM2M0XHVjYzI5XHVkNTVjXHViMmU0LiBcdWM2YjBcdWI5YWNcdWI4NWMgXHViY2Y0XHViMGI0XHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWM2YjBcdWI5YWNcdWM1ZDBcdWMxMWMgXHVjNmQwXHVjMjJkXHVjNzc0XHViOTdjIFx1YmQ4OFx1YjdlY1x1YzYyNFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgXHViYjM0XHVjMmRjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDQgXHViOWNjXHVkMDdjIFx1YjllNFx1YzZiMCBcdWM3OTFcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzg4NVx1Yzc0NCBcdWI5ZTRcdWM2YjAgXHVjODhiXHVjNTQ0XHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzViOFx1YzgxYyBcdWFjMDBcdWM1N2MgXHViNDE4XHViMjk0XHVjOWMwXHViOTdjIFx1YmFhOFx1Yjk3NFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzZkMFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWQwZGMgXHViMmU4XHVjOWMwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzViOFx1YzgxYyBcdWIzYzRcdWNjMjlcdWQ1NThcdWJhNzQgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI5N2MgXHViY2ZjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM1NGMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNmQwXHVjMjJkXHVjNzc0XHVhYzAwIFx1YzBkZFx1ZDBkYyBcdWJkODBcdWM5YzBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgwNFx1Y2NiNCBcdWMyZGNcdWFjMDQgVCAoMSAmbGU7IFQgJmxlOyAxLDAwMCwwMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBrXHViYzg4XHVjOWY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc1OCBcdWM4MTVcdWJjZjQgQTxzdWI+azxcL3N1Yj5cdWM2NDAgQjxzdWI+azxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEE8c3ViPms8XC9zdWI+LCBCPHN1Yj5rPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE0gJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBrXHViYzg4XHVjOWY4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yzc1OCBcdWM4MTVcdWJjZjQgQzxzdWI+azxcL3N1Yj5cdWM2NDAgRDxzdWI+azxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEM8c3ViPms8XC9zdWI+LCBEPHN1Yj5rPFwvc3ViPiwgJmxlOyAxLDAwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NzQgXHVjNmIwXHViOWFjXHViODVjIFx1YjRlNFx1YzViNFx1YWMwMFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzRcdWM3OTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NzQgXHVjMGRkXHVkMGRjIFx1YjJlOFx1YzljMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiXHJcbjxwPlxyXG5cdFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzc0IFx1YzEzOCBcdWFjMWMgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4ODVcdWM3NDAgXHVkNTVjIFx1YjljOFx1YjlhY1x1YjJlNC4gXHVjNzc0IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YWMwMCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjNjJjXHViNzdjXHVjMTFjIFx1Y2NhYiBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViNTMwXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgM1x1Y2QwOFx1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyA0XHVjZDA4XHVjNWQwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjUzMFx1YmE3MCwgNVx1Y2QwOFx1YzVkMCBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBhY1x1YzcyMVx1YzBhY1x1YjI5NCBcdWJiMzhcdWM3NDQgXHVjNWYwXHVjOWMwIDVcdWNkMDhcdWFjMDAgXHVjOWMwXHViMGFjXHVjNzQ0IFx1YjU0YywgXHVjMGRkXHVkMGRjIFx1YjJlOFx1YzljMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM2NDBcdWMxMWMgXHVjY2FiIFx1YzZkMFx1YzIyZFx1Yzc3NFx1Yjk3YyBcdWM2YjBcdWI5YWNcdWI4NWMgXHViM2NjXHViODI0XHViY2Y0XHViMGI0XHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzQ0IFx1YzBkZFx1ZDBkYyBcdWIyZThcdWM5YzBcdWI4NWMgXHViZDg4XHViN2VjXHVjNjI4XHViMmU0LiBcdWM3NzQgXHVjMmRjXHVhYzA0XHViZDgwXHVkMTMwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjODg1XHVjNzQ0IFx1YmNmYyBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3NDAgNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYjM4XHVjNzQ0IFx1YzVmMCBcdWMyZGNcdWFjMDRcdWJkODBcdWQxMzAgMTBcdWNkMDhcdWFjMDAgXHVjOWMwXHViMDk4XHViYTc0IFx1YjNjNFx1YWQ2Y1x1Yjk3YyBcdWNjM2VcdWFjZTAgXHVjY2FiIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzBcdWFjZTAsIDExXHVjZDA4XHVjNWQwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjZjU0XHVjZjU0XHViMTFiLCAxMlx1Y2QwOFx1YzVkMCBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWI1MzRcdWIyZTQuIFx1Yzc3NFx1YzgxYyBcdWMwYWNcdWM3MjFcdWMwYWNcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjQwXHVjMTFjIFx1YjJlNFx1YzJkYyBcdWM2ZDBcdWMyMmRcdWM3NzRcdWI5N2MgXHVjNmIwXHViOWFjXHViODVjIFx1YjNjY1x1YjgyNCBcdWJjZjRcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU1ZBREEiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBsb2NhbCB6b28gaGFzIGFjcXVpcmVkIGEgbGFyZ2Ugb3BlbiBnYXJkZW4gaW4gd2hpY2ggYW5pbWFscyBtYXkgZnJlZWx5IG1vdmUgYXMgaW4gdGhlaXIgbmF0dXJhbCBoYWJpdGF0cyBhbmQgZW50ZXJ0YWluIHZpc2l0b3JzIHdpdGggdGhlaXIgdXN1YWwgc2hlbmFuaWdhbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBtb3N0IHBvcHVsYXIgYW5pbWFscyBhcmUgbW9ua2V5cy4gV2l0aCB0aGVpciBjbGltYmluZyBhbmQganVtcGluZyBhbmQgb3RoZXIgc2tpbGxzLCB0aGV5IGRlbGlnaHQgb2xkIGFuZCB5b3VuZyB2aXNpdG9ycyBhbGlrZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T25lIHNwZWNpZXMgb2YgbW9ua2V5IGhhcyBzcGVjaWFsaXplZCBpbiBjbGltYmluZyB0YWxsIHRyZWVzIGFuZCBwaWNraW5nIG9mZiBjb2NvbnV0cy4gQW5vdGhlciBzcGVjaWVzIGhhcyBzcGVjaWFsaXplZCBpbiBicmVha2luZyB0aGVtIG9wZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOIG1vbmtleXMgb2YgdGhlIGZpcnN0IHR5cGUgKG51bWJlcmVkIDEgdGhyb3VnaCBOKSBhbmQgTSBtb25rZXlzIG9mIHRoZSBzZWNvbmQgdHlwZSAobnVtYmVyZWQgMSB0aHJvdWdoIE0pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Nb25rZXkgayBvZiB0aGUgZmlyc3QgdHlwZSB0YWtlcyBBPHN1Yj5rPFwvc3ViPiBzZWNvbmRzIHRvIGZpbmQgYSBnb29kIHNwb3Qgb24gdGhlIHRyZWUsIGFmdGVyIHdoaWNoIGl0IHBpY2tzIG9mZiBpdHMgZmlyc3QgY29jb251dC4gQWZ0ZXIgdGhhdCB0aGUgbW9ua2V5IHByb2R1Y2VzIGEgbmV3IGNvY29udXQgZXZlcnkgQjxzdWI+azxcL3N1Yj4gc2Vjb25kcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TW9ua2V5IGsgb2YgdGhlIHNlY29uZCB0eXBlIHRha2VzIEM8c3ViPms8XC9zdWI+IHNlY29uZHMgdG8gZmluZCBhIGdvb2QgdG9vbCBmb3Igb3BlbmluZyB0aGUgY29jb251dHMsIGFmdGVyIHdoaWNoIGl0IG9wZW5zIGl0cyBmaXJzdCBjb2NvbnV0LiBBZnRlciB0aGF0IHRoZSBtb25rZXkgb3BlbnMgYW5vdGhlciBjb2NvbnV0IGV2ZXJ5IEQ8c3ViPms8XC9zdWI+IHNlY29uZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIHRoZSBzZWNvbmQgdHlwZSBvZiBtb25rZXkgaXMgZXh0cmVtZWx5IGFnZ3Jlc3NpdmUgc28gdGhlIHR3byB0eXBlcyBtYXkgbm90IGJlIGluIHRoZSBnYXJkZW4gYXQgdGhlIHNhbWUgdGltZS4gVGhlcmVmb3JlLCB6b28ga2VlcGVycyB3aWxsIGNoYXNlIGF3YXkgdGhlIGZpcnN0IHR5cGUgb2YgbW9ua2V5cyBhcyBzb29uIGFzIHRoZXkgaGF2ZSBwaWNrZWQgb2ZmIGFsbCB0aGUgY29jb251dHMuIFNpbWlsYXJseSwgaWYgbW9ua2V5cyBvZiB0aGUgc2FtZSB0eXBlIHN0YXkgdG9vIGxvbmcgYWZ0ZXIgb3BlbmluZyBhbGwgdGhlIGNvY29udXRzLCBmaWdodHMgd2lsbCBlbnN1ZS4gQmVjYXVzZSBvZiB0aGF0LCB6b28ga2VlcGVycyB3aWxsIHNlbmQgdGhlbSBhd2F5IGFzIHNvb24gYXMgdGhleSBoYXZlIG9wZW5lZCBhbGwgdGhlIGNvY29udXRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgem9vIGtlZXBlcnMgZmlyc3QgYXJyaXZlIGltbWVkaWF0ZWx5IGFmdGVyIGFsbCBjb2NvbnV0cyBoYXZlIGJlZW4gcGlja2VkLCBhbmQgYWdhaW4gaW1tZWRpYXRlbHkgYWZ0ZXIgdGhlIG1vbmtleXMgb3BlbiB0aGVtIGFsbC4gVGhlIHRpbWUgbmVlZGVkIGZvciBtb25rZXlzIHRvIGVudGVyIG9yIGxlYXZlIHRoZSBnYXJkZW4gaXMgYWxzbyBuZWdsaWdpYmx5IHNtYWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ub21pc2xhdiBlc3BlY2lhbGx5IGxpa2VzIHRoZSBzZWNvbmQgdHlwZSBvZiBtb25rZXksIGJ1dCBjYW4gbmV2ZXIgZ3Vlc3Mgd2hlbiB0byBhcnJpdmUgaW4gb3JkZXIgdG8gc2VlIHRoZW0uIEhlbHAgaGltIGNhbGN1bGF0ZSB0aGUgdGltZSB3aGVuIHRoZSBzZWNvbmQgdHlwZSBhcnJpdmVzIGlmIGhlIGtub3dzIHRoZSB0b3RhbCB0aW1lIHRoYXQgbW9ua2V5cyBzcGVudCBpbiB0aGUgZ2FyZGVuLCBidXQgZG9lcyBub3Qga25vdyB0aGUgbnVtYmVyIG9mIGNvY29udXRzIGluIHRoZSBnYXJkZW4uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBUICgxICZsZTsgVCAmbGU7IDEgMDAwIDAwMCAwMDApLCB0aGUgdG90YWwgdGltZSB0aGF0IG1vbmtleXMgc3BlbnQgaW4gdGhlIGdhcmRlbiwgaW4gc2Vjb25kcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgbW9ua2V5cyBvZiB0aGUgZmlyc3QgdHlwZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIEE8c3ViPms8XC9zdWI+IGFuZCBCPHN1Yj5rPFwvc3ViPiAoMSAmbGU7IEE8c3ViPms8XC9zdWI+LCBCPHN1Yj5rPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDApLCBob3cgZmFzdCBtb25rZXkgayBvZiB0aGUgZmlyc3QgdHlwZSBpcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyB0aGUgaW50ZWdlciBNICgxICZsZTsgTSAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgbW9ua2V5cyBvZiB0aGUgc2Vjb25kIHR5cGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBDPHN1Yj5rPFwvc3ViPiBhbmQgRDxzdWI+azxcL3N1Yj4gKDEgJmxlOyBDPHN1Yj5rPFwvc3ViPiwgRDxzdWI+azxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwKSwgaG93IGZhc3QgbW9ua2V5IGsgb2YgdGhlIHNlY29uZCB0eXBlIGlzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHNlY29uZHMgYmV0d2VlbiB0aGUgYXJyaXZhbCBvZiB0aGUgZmlyc3QgdHlwZSBvZiBtb25rZXlzIGFuZCB0aGUgYXJyaXZhbCBvZiB0aGUgc2Vjb25kIHR5cGUuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBleGFtcGxlLCBpdCB0dXJucyBvdXQgdGhlcmUgYXJlIHRocmVlIGNvY29udXRzIGluIHRoZSBnYXJkZW46Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIG1vbmtleSBvZiB0aGUgZmlyc3QgdHlwZSBwaWNrcyBvZmYgdGhlIGZpcnN0IGNvY29udXQgMyBzZWNvbmRzIGFmdGVyIHRoZSBnYXJkZW4gd2FzIG9wZW5lZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIG1vbmtleSBwaWNrcyBvZmYgdGhlIHNlY29uZCBjb2NvbnV0IDQgc2Vjb25kcyBhZnRlciB0aGUgZ2FyZGVuIGlzIG9wZW5lZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIG1vbmtleSBwaWNrcyBvZmYgdGhlIHRoaXJkIGNvY29udXQgNSBzZWNvbmRzIGFmdGVyIHRoZSBnYXJkZW4gaXMgb3BlbmVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5ab28ga2VlcGVycyBjb21lIGluIGFuZCBlc2NvcnQgdGhlIG1vbmtleSBvdXQuIFRoZSBtb25rZXkgb2YgdGhlIHNlY29uZCB0eXBlIGFycml2ZXMuIFRoZSBvdXRwdXQgaXMgNSBiZWNhdXNlIHRoaXMgaXMgd2hlbiBUb21pc2xhdiB3YW50cyB0byBhcnJpdmUuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBtb25rZXkgb2YgdGhlIHNlY29uZCB0eXBlIG9wZW5zIHRoZSBmaXJzdCBjb2NvbnV0IDEwIHNlY29uZHMgYWZ0ZXIgdGhlIGdhcmRlbiB3YXMgb3BlbmVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbW9ua2V5IG9wZW5zIHRoZSBzZWNvbmQgY29jb251dCAxMSBzZWNvbmRzIGFmdGVyIHRoZSBnYXJkZW4gd2FzIG9wZW5lZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIG1vbmtleSBvcGVucyB0aGUgdGhpcmQgY29jb251dCAxMiBzZWNvbmRzIGFmdGVyIHRoZSBnYXJkZW4gd2FzIG9wZW5lZC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Wm9vIGtlZXBlcnMgY29tZSBpbiBhbmQgZXNjb3J0IHRoZSBtb25rZXkgb3V0LiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: doju