시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 60 4 4 7.143%

문제

동규는 큰 벽을 2일동안 만들려고 한다.

가게에는 N종류의 블록이 있다. 이 블록의 개수는 매우 많기 때문에, 품절되는 경우는 없다. 각 블록의 가격은 Ci이며, 1*1*Di 크기이다.

2일 중 하루는 모든 블록을 수평으로 쌓을 것이고, 다른 날에는 수직으로 쌓을 것이다.

벽은 L미터 크기의 평평한 땅 위에 만들 것이다. 벽은 실루엣으로 묘사한다.

실루엣은 (x1, y1), (x2, y2), ..., (Xm, Ym)와 같이 좌표의 연속으로 표현하고, 벽의 위쪽 경계선이다.

실루엣에 대해서 좀 더 자세히 설명하면 다음과 같다.

M은 짝수이다.

x1 = 0, xm = L

x2k-1 < x2k, x2k = x2k+1

y2k-1 = y2k

예를 들어, 길이가 7인 벽이 있을 때, 왼쪽 그림을 실루엣으로 표현하면, (0,2), (3,2), (3,1), (5,1), (5,3), (7,3)이며, 오른쪽 그림은 (0,4), (2,4), (2,6), (7,6)이다.

현재 가게에서 파는 블록의 정보와 첫째 날 완성한 벽의 실루엣과 둘째 날 완성한 벽의 실루엣이 주어졌을 때, 벽을 완성하는데 필요한 금액의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 벽의 길이 L이 주어진다. (2 ≤ L ≤ 109)

둘째 줄에는 블록 종류의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개의 줄에는 D와 C가 주어진다. D는 블록의 길이이고, C는 블록의 가격이다. (2 ≤ D ≤ 1,000, 1 ≤ C ≤ 1,000,000)

다음 줄에는 첫째 날 실루엣 점의 개수 M1이 주어진다. (2 ≤ M1 ≤ 100,000, M1은 짝수)

다음 M1개 줄에는, 첫째 날 실루엣의 좌표가 순서대로 주어진다. 좌표는 음이 아닌 정수이다.

다음 줄에는 둘째 날 실루엣 점의 개수 M2가 주어진다. (2 ≤ M2 ≤ 100,000, M2은 짝수)

다음 M2개 줄에는, 둘째 날 실루엣의 좌표가 순서대로 주어진다. 좌표는 음이 아닌 정수이다.

벽의 높이는 109를 넘지 않는다.

각각의 x좌표에 대해서, 첫째 날 벽의 실루엣의 높이는 둘째날 벽의 실루엣의 높이보다 작거나 같다.

출력

첫째 줄에 벽의 완성하는데 드는 최소 비용을 출력한다. 항상 벽을 만들 수 있는 경우만 입력으로 주어지며, 벽을 완성하는데 드는 최소 비용은 1018을 넘지 않는다.

예제 입력 1

7
2
2 5
3 7
6
0 2
3 2
3 1
5 1
5 3
7 3
4
0 4
2 4
2 6
7 6

예제 출력 1

92
W3sicHJvYmxlbV9pZCI6IjMxMDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYmQgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIzZDlcdWFkZGNcdWIyOTQgXHVkMDcwIFx1YmNiZFx1Yzc0NCAyXHVjNzdjXHViM2Q5XHVjNTQ4IFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMFx1YWM4Y1x1YzVkMFx1YjI5NCBOXHVjODg1XHViOTU4XHVjNzU4IFx1YmUxNFx1Yjg1ZFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YjllNFx1YzZiMCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ0ODhcdWM4MDhcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHVhYzAxIFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDAgQzxzdWI+aTxcL3N1Yj5cdWM3NzRcdWJhNzAsIDEqMSpEPHN1Yj5pPFwvc3ViPiBcdWQwNmNcdWFlMzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDJcdWM3N2MgXHVjOTExIFx1ZDU1OFx1YjhlOFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViZTE0XHViODVkXHVjNzQ0IFx1YzIxOFx1ZDNjOVx1YzczY1x1Yjg1YyBcdWMzMTNcdWM3NDQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHViMGEwXHVjNWQwXHViMjk0IFx1YzIxOFx1YzljMVx1YzczY1x1Yjg1YyBcdWMzMTNcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJjYmRcdWM3NDAgTFx1YmJmOFx1ZDEzMCBcdWQwNmNcdWFlMzBcdWM3NTggXHVkM2M5XHVkM2M5XHVkNTVjIFx1YjU0NSBcdWM3MDRcdWM1ZDAgXHViOWNjXHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViY2JkXHVjNzQwIFx1YzJlNFx1YjhlOFx1YzVlM1x1YzczY1x1Yjg1YyBcdWJiMThcdWMwYWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzJlNFx1YjhlOFx1YzVlM1x1Yzc0MCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSwgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPiksIC4uLiwgKFg8c3ViPm08XC9zdWI+LCBZPHN1Yj5tPFwvc3ViPilcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhY2UwLCBcdWJjYmRcdWM3NTggXHVjNzA0XHVjYWJkIFx1YWNiZFx1YWNjNFx1YzEyMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMmU0XHViOGU4XHVjNWUzXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM4ODAgXHViMzU0IFx1Yzc5MFx1YzEzOFx1ZDc4OCBcdWMxMjRcdWJhODVcdWQ1NThcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0TVx1Yzc0MCBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0eDxzdWI+MTxcL3N1Yj4gPSAwLCB4PHN1Yj5tPFwvc3ViPiA9IEw8XC9wPlxyXG48cD5cclxuXHR4PHN1Yj4yay0xPFwvc3ViPiAmbHQ7IHg8c3ViPjJrPFwvc3ViPiwgeDxzdWI+Mms8XC9zdWI+ID0geDI8c3ViPmsrMTxcL3N1Yj48XC9wPlxyXG48cD5cclxuXHR5PHN1Yj4yay0xPFwvc3ViPiA9IHk8c3ViPjJrPFwvc3ViPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFlMzhcdWM3NzRcdWFjMDAgN1x1Yzc3OCBcdWJjYmRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0NCBcdWMyZTRcdWI4ZThcdWM1ZTNcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHViYTc0LCAoMCwyKSwgKDMsMiksICgzLDEpLCAoNSwxKSwgKDUsMyksICg3LDMpXHVjNzc0XHViYTcwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwICgwLDQpLCAoMiw0KSwgKDIsNiksICg3LDYpXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2NrLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDU1MnB4OyBoZWlnaHQ6IDE5M3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ2MDRcdWM3YWMgXHVhYzAwXHVhYzhjXHVjNWQwXHVjMTFjIFx1ZDMwY1x1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVjODE1XHViY2Y0XHVjNjQwIFx1Y2NhYlx1YzlmOCBcdWIwYTAgXHVjNjQ0XHVjMTMxXHVkNTVjIFx1YmNiZFx1Yzc1OCBcdWMyZTRcdWI4ZThcdWM1ZTNcdWFjZmMgXHViNDU4XHVjOWY4IFx1YjBhMCBcdWM2NDRcdWMxMzFcdWQ1NWMgXHViY2JkXHVjNzU4IFx1YzJlNFx1YjhlOFx1YzVlM1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJjYmRcdWM3NDQgXHVjNjQ0XHVjMTMxXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFlMDhcdWM1NjFcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjYmRcdWM3NTggXHVhZTM4XHVjNzc0IExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViZTE0XHViODVkIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IERcdWM2NDAgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIERcdWIyOTQgXHViZTE0XHViODVkXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YWNlMCwgQ1x1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzc0XHViMmU0LiAoMiAmbGU7IEQgJmxlOyAxLDAwMCwgMSAmbGU7IEMgJmxlOyAxLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjY2FiXHVjOWY4IFx1YjBhMCBcdWMyZTRcdWI4ZThcdWM1ZTMgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBNMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTTxzdWI+MTxcL3N1Yj4gJmxlOyAxMDAsMDAwLCBNPHN1Yj4xPFwvc3ViPlx1Yzc0MCBcdWM5ZGRcdWMyMTgpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNPHN1Yj4xPFwvc3ViPlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1Y2NhYlx1YzlmOCBcdWIwYTAgXHVjMmU0XHViOGU4XHVjNWUzXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDU4XHVjOWY4IFx1YjBhMCBcdWMyZTRcdWI4ZThcdWM1ZTMgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBNPHN1Yj4yPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTTxzdWI+MjxcL3N1Yj4gJmxlOyAxMDAsMDAwLCBNPHN1Yj4yPFwvc3ViPlx1Yzc0MCBcdWM5ZGRcdWMyMTgpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNPHN1Yj4yPFwvc3ViPlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1YjQ1OFx1YzlmOCBcdWIwYTAgXHVjMmU0XHViOGU4XHVjNWUzXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmNiZFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgMTA8c3VwPjk8XC9zdXA+XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCB4XHVjODhjXHVkNDVjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjY2FiXHVjOWY4IFx1YjBhMCBcdWJjYmRcdWM3NTggXHVjMmU0XHViOGU4XHVjNWUzXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWI0NThcdWM5ZjhcdWIwYTAgXHViY2JkXHVjNzU4IFx1YzJlNFx1YjhlOFx1YzVlM1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNiZFx1Yzc1OCBcdWM2NDRcdWMxMzFcdWQ1NThcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViY2JkXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWJjYmRcdWM3NDQgXHVjNjQ0XHVjMTMxXHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQwIDEwPHN1cD4xODxcL3N1cD5cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDSUdMRSIsImRlc2NyaXB0aW9uIjoiPHA+TGp1Ym8gaXMgcGxhbm5pbmcgdG8gYnVpbGQgYSBiaWcgd2FsbCBpbiBqdXN0IHR3byBkYXlzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHN0b3JlIG9mZmVycyBOIGRpc3RpbmN0IHR5cGVzIG9kIGJyaWNrcyBpbiB1bmxpbWl0ZWQgc3VwcGx5LiBFYWNoIGJyaWNrIHR5cGUgaGFzIHNwZWNpZmljIHByaWNlIEM8c3ViPmk8XC9zdWI+IGFuZCBkaW1lbnNpb25zIDEmdGltZXM7MSZ0aW1lcztEPHN1Yj5pPFwvc3ViPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T25lIGRheSBManVibyB3aWxsIHBsYWNlIGJyaWNrcyBpbiB0aGUgd2FsbCBob3Jpem9udGFsbHksIHdoaWxlIHRoZSBvdGhlciBkYXkgaGUgd2lsbCBwbGFjZSBicmlja3MgdmVydGljYWxseS4gSGUgY2FuIGNob29zZSBpZiBoZSB3aWxsIHBsYWNlIGJyaWNrcyBob3Jpem9udGFsbHkgdGhlIGZpcnN0IGRheSBvciB0aGUgc2Vjb25kIGRheSBhbmQgaGUgd2lsbCwgb2YgY291cnNlLCBjaG9vc2UgdGhlIGNoZWFwZXIgdmFyaWFudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHdhbGwgbGllcyBvbiB0aGUgZmxhdCBncm91bmQgYW5kIGlzIEwgbWV0ZXJzIGxvbmcsIGFuZCBjYW4gYmUgZGVzY3JpYmVkIGJ5IHNpbGhvdWV0dGUsIGEgc2VxdWVuY2Ugb2YgcG9pbnRzICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pLCAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KSwgLi4uLCAoeDxzdWI+TTxcL3N1Yj4sIHk8c3ViPk08XC9zdWI+KSB0aGF0IGZvbGxvd3MgdGhlIHVwcGVyIGJvcmRlciBvZiB0aGUgd2FsbC4gU2lsaG91ZXR0ZSBiZWdpbnMgd2l0aCB1cHBlciBsZWZ0IGNvcm5lciBvZiB0aGUgd2FsbCBhbmQgZW5kcyB3aXRoIHVwcGVyIHJpZ2h0IGNvcm5lciBvZiB0aGUgd2FsbC4gU3BlY2lmaWNhbGx5OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk0gaXMgYW4gZXZlbiBudW1iZXImbmJzcDs8XC9saT5cclxuXHQ8bGk+eDxzdWI+MTxcL3N1Yj4gPSAwLCB4PHN1Yj5NPFwvc3ViPiA9IEwmbmJzcDs8XC9saT5cclxuXHQ8bGk+eDxzdWI+MmstMTxcL3N1Yj4gJmx0OyB4PHN1Yj4yazxcL3N1Yj4gLCB4PHN1Yj4yazxcL3N1Yj4gPSB4PHN1Yj4yaysxPFwvc3ViPiwgZm9yIGVhY2ggayZuYnNwOzxcL2xpPlxyXG5cdDxsaT55PHN1Yj4yay0xPFwvc3ViPiA9IHk8c3ViPjJrPFwvc3ViPiwgZm9yIGVhY2ggayZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBhIHdhbGwgb2YgbGVuZ3RoIDcgaW4gdGhlIGxlZnQgaWxsdXN0cmF0aW9uIGlzIGRlc2NyaWJlZCBieSBzaWxob3VldHRlICgwLCAyKSwgKDMsIDIpLCAoMywgMSksICg1LCAxKSwgKDUsIDMpLCAoNywgMyksIHdoaWxlIHRoZSB3YWxsIG9uIHRoZSByaWdodCBpbGx1c3RyYXRpb24gaXMgZGVzY3JpYmVkIGJ5IHNpbGhvdWV0dGUgKDAsIDQpLCAoMiwgNCksICgyLCA2KSwgKDcsIDYpLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2NrLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5M3B4OyBvcGFjaXR5OjAuOTsgd2lkdGg6NTUycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGRhdGEgZm9yIGF2YWlsYWJsZSBicmljayB0eXBlcyBhcyB3ZWxsIGFzIHRoZSB3YWxsIHNpbGhvdWV0dGUgYWZ0ZXIgdGhlIGZpcnN0IGRheSBhbmQgdGhlIGZpbmFsIHdhbGwgc2lsaG91ZXR0ZSwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIGNvc3Qgb2YgdGhlIGNoZWFwZXN0IHBvc3NpYmxlIHRvdGFsIHByaWNlIHRvIGJ1aWxkIGEgd2FsbCBpbiB0d28gZGF5cyBhcyBkZXNjcmliZWQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBMICgyICZsZTsgTCAmbGU7IDEwPHN1cD45PFwvc3VwPiksIHdhbGwgbGVuZ3RoLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIGJyaWNrIHR5cGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gdHdvIG5hdHVyYWwgbnVtYmVycyBlYWNoIEQgYW5kIEMgKDIgJmxlOyBEICZsZTsgMTAwMCwgMSAmbGU7IEMgJmxlOyAxIDAwMCAwMDApLCB0aGUgYnJpY2sgbGVuZ3RoIGFuZCBwcmljZSBmb3IgZWFjaCBicmljayB0eXBlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIG9uZSBldmVuIGludGVnZXIgTTEgKDIgJmxlOyBNPHN1Yj4xPFwvc3ViPiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHBvaW50cyBvbiBhIHdhbGwgc2lsaG91ZXR0ZSBhZnRlciB0aGUgZmlyc3QgZGF5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBNPHN1Yj4xPFwvc3ViPiBsaW5lcyBjb250YWlucyBwb2ludHMgY29vcmRpbmF0ZXMsIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgZWFjaC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBvbmUgZXZlbiBpbnRlZ2VyIE08c3ViPjI8XC9zdWI+ICgyICZsZTsgTTxzdWI+MjxcL3N1Yj4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBwb2ludHMgb24gYSB3YWxsIHNpbGhvdWV0dGUgYWZ0ZXIgdGhlIHNlY29uZCBkYXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE08c3ViPjI8XC9zdWI+IGxpbmVzIGNvbnRhaW5zIHBvaW50cyBjb29yZGluYXRlcywgdHdvIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBlYWNoLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XYWxsIGhlaWdodCB3aWxsIG5vdCBleGNlZWQgMTA8c3VwPjk8XC9zdXA+LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCB4IGNvb3JkaW5hdGUsIHRoZSBoZWlnaHQgb2YgZmlyc3Qgd2FsbCBzaWxob3VldHRlIHdpbGwgYmUgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIHRoZSBoZWlnaHQgb2YgdGhlIHNlY29uZCB3YWxsIHNpbGhvdWV0dGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgbWluaW11bSBjb3N0IHRvIGJ1aWxkIHRoZSB3YWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgaW5wdXQgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCBpdCB3aWxsIGJlIHBvc3NpYmxlIHRvIGJ1aWxkIHRoZSB3YWxsIGluIHRoZSB3YXkgZGVzY3JpYmVkLCBhbmQgdGhlIG1pbmltdW0gY29zdCB3aWxsIG5vdCBleGNlZWQgMTA8c3VwPjE4PFwvc3VwPi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Final Exam #2 1번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: doju