시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 3 3 6.383%

문제

동규는 큰 벽을 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
W3sicHJvYmxlbV9pZCI6IjMxMDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYmQgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWIzZDlcdWFkZGNcdWIyOTQgXHVkMDcwIFx1YmNiZFx1Yzc0NCAyXHVjNzdjXHViM2Q5XHVjNTQ4IFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMFx1YWM4Y1x1YzVkMFx1YjI5NCBOXHVjODg1XHViOTU4XHVjNzU4IFx1YmUxNFx1Yjg1ZFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YjllNFx1YzZiMCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ0ODhcdWM4MDhcdWI0MThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHVhYzAxIFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDAgQzxzdWI+aTxcL3N1Yj5cdWM3NzRcdWJhNzAsIDEqMSpEPHN1Yj5pPFwvc3ViPiBcdWQwNmNcdWFlMzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDJcdWM3N2MgXHVjOTExIFx1ZDU1OFx1YjhlOFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViZTE0XHViODVkXHVjNzQ0IFx1YzIxOFx1ZDNjOVx1YzczY1x1Yjg1YyBcdWMzMTNcdWM3NDQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHViMGEwXHVjNWQwXHViMjk0IFx1YzIxOFx1YzljMVx1YzczY1x1Yjg1YyBcdWMzMTNcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJjYmRcdWM3NDAgTFx1YmJmOFx1ZDEzMCBcdWQwNmNcdWFlMzBcdWM3NTggXHVkM2M5XHVkM2M5XHVkNTVjIFx1YjU0NSBcdWM3MDRcdWM1ZDAgXHViOWNjXHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViY2JkXHVjNzQwIFx1YzJlNFx1YjhlOFx1YzVlM1x1YzczY1x1Yjg1YyBcdWJiMThcdWMwYWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzJlNFx1YjhlOFx1YzVlM1x1Yzc0MCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSwgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPiksIC4uLiwgKFg8c3ViPm08XC9zdWI+LCBZPHN1Yj5tPFwvc3ViPilcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhY2UwLCBcdWJjYmRcdWM3NTggXHVjNzA0XHVjYWJkIFx1YWNiZFx1YWNjNFx1YzEyMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMmU0XHViOGU4XHVjNWUzXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM4ODAgXHViMzU0IFx1Yzc5MFx1YzEzOFx1ZDc4OCBcdWMxMjRcdWJhODVcdWQ1NThcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0TVx1Yzc0MCBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0eDxzdWI+MTxcL3N1Yj4gPSAwLCB4PHN1Yj5tPFwvc3ViPiA9IEw8XC9wPlxyXG48cD5cclxuXHR4PHN1Yj4yay0xPFwvc3ViPiAmbHQ7IHg8c3ViPjJrPFwvc3ViPiwgeDxzdWI+Mms8XC9zdWI+ID0geDI8c3ViPmsrMTxcL3N1Yj48XC9wPlxyXG48cD5cclxuXHR5PHN1Yj4yay0xPFwvc3ViPiA9IHk8c3ViPjJrPFwvc3ViPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFlMzhcdWM3NzRcdWFjMDAgN1x1Yzc3OCBcdWJjYmRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0NCBcdWMyZTRcdWI4ZThcdWM1ZTNcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHViYTc0LCAoMCwyKSwgKDMsMiksICgzLDEpLCAoNSwxKSwgKDUsMyksICg3LDMpXHVjNzc0XHViYTcwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwICgwLDQpLCAoMiw0KSwgKDIsNiksICg3LDYpXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Jsb2NrLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDU1MnB4OyBoZWlnaHQ6IDE5M3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ2MDRcdWM3YWMgXHVhYzAwXHVhYzhjXHVjNWQwXHVjMTFjIFx1ZDMwY1x1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVjODE1XHViY2Y0XHVjNjQwIFx1Y2NhYlx1YzlmOCBcdWIwYTAgXHVjNjQ0XHVjMTMxXHVkNTVjIFx1YmNiZFx1Yzc1OCBcdWMyZTRcdWI4ZThcdWM1ZTNcdWFjZmMgXHViNDU4XHVjOWY4IFx1YjBhMCBcdWM2NDRcdWMxMzFcdWQ1NWMgXHViY2JkXHVjNzU4IFx1YzJlNFx1YjhlOFx1YzVlM1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJjYmRcdWM3NDQgXHVjNjQ0XHVjMTMxXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFlMDhcdWM1NjFcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjYmRcdWM3NTggXHVhZTM4XHVjNzc0IExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViZTE0XHViODVkIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IERcdWM2NDAgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIERcdWIyOTQgXHViZTE0XHViODVkXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YWNlMCwgQ1x1YjI5NCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzc0XHViMmU0LiAoMiAmbGU7IEQgJmxlOyAxLDAwMCwgMSAmbGU7IEMgJmxlOyAxLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjY2FiXHVjOWY4IFx1YjBhMCBcdWMyZTRcdWI4ZThcdWM1ZTMgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBNMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTTxzdWI+MTxcL3N1Yj4gJmxlOyAxMDAsMDAwLCBNPHN1Yj4xPFwvc3ViPlx1Yzc0MCBcdWM5ZGRcdWMyMTgpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNPHN1Yj4xPFwvc3ViPlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1Y2NhYlx1YzlmOCBcdWIwYTAgXHVjMmU0XHViOGU4XHVjNWUzXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDU4XHVjOWY4IFx1YjBhMCBcdWMyZTRcdWI4ZThcdWM1ZTMgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBNPHN1Yj4yPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTTxzdWI+MjxcL3N1Yj4gJmxlOyAxMDAsMDAwLCBNPHN1Yj4yPFwvc3ViPlx1Yzc0MCBcdWM5ZGRcdWMyMTgpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNPHN1Yj4yPFwvc3ViPlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQsIFx1YjQ1OFx1YzlmOCBcdWIwYTAgXHVjMmU0XHViOGU4XHVjNWUzXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmNiZFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgMTA8c3VwPjk8XC9zdXA+XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCB4XHVjODhjXHVkNDVjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjY2FiXHVjOWY4IFx1YjBhMCBcdWJjYmRcdWM3NTggXHVjMmU0XHViOGU4XHVjNWUzXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWI0NThcdWM5ZjhcdWIwYTAgXHViY2JkXHVjNzU4IFx1YzJlNFx1YjhlOFx1YzVlM1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNiZFx1Yzc1OCBcdWM2NDRcdWMxMzFcdWQ1NThcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViY2JkXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWJjYmRcdWM3NDQgXHVjNjQ0XHVjMTMxXHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQwIDEwPHN1cD4xODxcL3N1cD5cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ0lHTEUiLCJkZXNjcmlwdGlvbiI6IjxwPkxqdWJvIGlzIHBsYW5uaW5nIHRvIGJ1aWxkIGEgYmlnIHdhbGwgaW4ganVzdCB0d28gZGF5cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzdG9yZSBvZmZlcnMgTiBkaXN0aW5jdCB0eXBlcyBvZCBicmlja3MgaW4gdW5saW1pdGVkIHN1cHBseS4gRWFjaCBicmljayB0eXBlIGhhcyBzcGVjaWZpYyBwcmljZSBDPHN1Yj5pPFwvc3ViPiBhbmQgZGltZW5zaW9ucyAxJnRpbWVzOzEmdGltZXM7RDxzdWI+aTxcL3N1Yj4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uZSBkYXkgTGp1Ym8gd2lsbCBwbGFjZSBicmlja3MgaW4gdGhlIHdhbGwgaG9yaXpvbnRhbGx5LCB3aGlsZSB0aGUgb3RoZXIgZGF5IGhlIHdpbGwgcGxhY2UgYnJpY2tzIHZlcnRpY2FsbHkuIEhlIGNhbiBjaG9vc2UgaWYgaGUgd2lsbCBwbGFjZSBicmlja3MgaG9yaXpvbnRhbGx5IHRoZSBmaXJzdCBkYXkgb3IgdGhlIHNlY29uZCBkYXkgYW5kIGhlIHdpbGwsIG9mIGNvdXJzZSwgY2hvb3NlIHRoZSBjaGVhcGVyIHZhcmlhbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB3YWxsIGxpZXMgb24gdGhlIGZsYXQgZ3JvdW5kIGFuZCBpcyBMIG1ldGVycyBsb25nLCBhbmQgY2FuIGJlIGRlc2NyaWJlZCBieSBzaWxob3VldHRlLCBhIHNlcXVlbmNlIG9mIHBvaW50cyAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSwgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPiksIC4uLiwgKHg8c3ViPk08XC9zdWI+LCB5PHN1Yj5NPFwvc3ViPikgdGhhdCBmb2xsb3dzIHRoZSB1cHBlciBib3JkZXIgb2YgdGhlIHdhbGwuIFNpbGhvdWV0dGUgYmVnaW5zIHdpdGggdXBwZXIgbGVmdCBjb3JuZXIgb2YgdGhlIHdhbGwgYW5kIGVuZHMgd2l0aCB1cHBlciByaWdodCBjb3JuZXIgb2YgdGhlIHdhbGwuIFNwZWNpZmljYWxseTombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5NIGlzIGFuIGV2ZW4gbnVtYmVyJm5ic3A7PFwvbGk+XHJcblx0PGxpPng8c3ViPjE8XC9zdWI+ID0gMCwgeDxzdWI+TTxcL3N1Yj4gPSBMJm5ic3A7PFwvbGk+XHJcblx0PGxpPng8c3ViPjJrLTE8XC9zdWI+ICZsdDsgeDxzdWI+Mms8XC9zdWI+ICwgeDxzdWI+Mms8XC9zdWI+ID0geDxzdWI+MmsrMTxcL3N1Yj4sIGZvciBlYWNoIGsmbmJzcDs8XC9saT5cclxuXHQ8bGk+eTxzdWI+MmstMTxcL3N1Yj4gPSB5PHN1Yj4yazxcL3N1Yj4sIGZvciBlYWNoIGsmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgYSB3YWxsIG9mIGxlbmd0aCA3IGluIHRoZSBsZWZ0IGlsbHVzdHJhdGlvbiBpcyBkZXNjcmliZWQgYnkgc2lsaG91ZXR0ZSAoMCwgMiksICgzLCAyKSwgKDMsIDEpLCAoNSwgMSksICg1LCAzKSwgKDcsIDMpLCB3aGlsZSB0aGUgd2FsbCBvbiB0aGUgcmlnaHQgaWxsdXN0cmF0aW9uIGlzIGRlc2NyaWJlZCBieSBzaWxob3VldHRlICgwLCA0KSwgKDIsIDQpLCAoMiwgNiksICg3LCA2KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ibG9jay5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTNweDsgb3BhY2l0eTowLjk7IHdpZHRoOjU1MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBkYXRhIGZvciBhdmFpbGFibGUgYnJpY2sgdHlwZXMgYXMgd2VsbCBhcyB0aGUgd2FsbCBzaWxob3VldHRlIGFmdGVyIHRoZSBmaXJzdCBkYXkgYW5kIHRoZSBmaW5hbCB3YWxsIHNpbGhvdWV0dGUsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBjb3N0IG9mIHRoZSBjaGVhcGVzdCBwb3NzaWJsZSB0b3RhbCBwcmljZSB0byBidWlsZCBhIHdhbGwgaW4gdHdvIGRheXMgYXMgZGVzY3JpYmVkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgTCAoMiAmbGU7IEwgJmxlOyAxMDxzdXA+OTxcL3N1cD4pLCB3YWxsIGxlbmd0aC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBicmljayB0eXBlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBjb250YWluIHR3byBuYXR1cmFsIG51bWJlcnMgZWFjaCBEIGFuZCBDICgyICZsZTsgRCAmbGU7IDEwMDAsIDEgJmxlOyBDICZsZTsgMSAwMDAgMDAwKSwgdGhlIGJyaWNrIGxlbmd0aCBhbmQgcHJpY2UgZm9yIGVhY2ggYnJpY2sgdHlwZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBvbmUgZXZlbiBpbnRlZ2VyIE0xICgyICZsZTsgTTxzdWI+MTxcL3N1Yj4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBwb2ludHMgb24gYSB3YWxsIHNpbGhvdWV0dGUgYWZ0ZXIgdGhlIGZpcnN0IGRheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTTxzdWI+MTxcL3N1Yj4gbGluZXMgY29udGFpbnMgcG9pbnRzIGNvb3JkaW5hdGVzLCB0d28gbm9uLW5lZ2F0aXZlIGludGVnZXJzIGVhY2guJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgb25lIGV2ZW4gaW50ZWdlciBNPHN1Yj4yPFwvc3ViPiAoMiAmbGU7IE08c3ViPjI8XC9zdWI+ICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgcG9pbnRzIG9uIGEgd2FsbCBzaWxob3VldHRlIGFmdGVyIHRoZSBzZWNvbmQgZGF5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBNPHN1Yj4yPFwvc3ViPiBsaW5lcyBjb250YWlucyBwb2ludHMgY29vcmRpbmF0ZXMsIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgZWFjaC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2FsbCBoZWlnaHQgd2lsbCBub3QgZXhjZWVkIDEwPHN1cD45PFwvc3VwPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggeCBjb29yZGluYXRlLCB0aGUgaGVpZ2h0IG9mIGZpcnN0IHdhbGwgc2lsaG91ZXR0ZSB3aWxsIGJlIGxlc3MgdGhhbiBvciBlcXVhbCB0byB0aGUgaGVpZ2h0IG9mIHRoZSBzZWNvbmQgd2FsbCBzaWxob3VldHRlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlciwgdGhlIG1pbmltdW0gY29zdCB0byBidWlsZCB0aGUgd2FsbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIGlucHV0IGRhdGEgd2lsbCBiZSBzdWNoIHRoYXQgaXQgd2lsbCBiZSBwb3NzaWJsZSB0byBidWlsZCB0aGUgd2FsbCBpbiB0aGUgd2F5IGRlc2NyaWJlZCwgYW5kIHRoZSBtaW5pbXVtIGNvc3Qgd2lsbCBub3QgZXhjZWVkIDEwPHN1cD4xODxcL3N1cD4uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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