시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 65 47 36 72.000%

문제

고대에 유명한 조각가인 오세준은 또다른 걸작을 만들기 위한 준비 작업을 하고 있다. 그래서 가로 세로 크기가 W1×H1, W2×H2, ... Wn×Hn인 직사각형 모양의 대리석 석판이 여러 장 필요한 상태이다.

얼마 전, 세준이는 커다란 직사각형 석판을 받았다. 그래서 이것을 원하는 크기에 해당하는 석판들로 쪼개고 싶어한다. 석판은 임의의 정수 위치에서 가로나 세로로 완전히 잘라서 두 개의 직사각형 모양으로 자를 수 있다. 하지만 작은 석판들을 붙여서 큰 판으로 만들 수는 없다. 또한, 석판에는 일정한 방향으로 무늬가 있기 때문에, 회전해서 원하는 크기를 만들 수는 없다. 다시 말해, A×B라는 크기로 잘랐다면 이것을 B×A라는 크기에 맞추어 사용할 수는 없다는 뜻이다. 석판에서 원하는 크기에 해당하는 면을 모두 잘라 낸 뒤, 어느 크기로도 쪼갤 수 없어 남게 된 면들은 버려진다. 세준이는 원판을 어떻게 자르면 이러한 손실을 가능한 한 줄일 수 있을지 알고 싶어한다.

가로 길이가 21이고 세로 길이가 11인 커다란 석판을 예로 들어 보자. 그리고 우리에게 필요한 석판 크기의 종류가 10×4, 6×2, 7×5, 그리고 15×10이라고 가정하자. 이 경우 석판을 아래 그림과 같이 자르면, 각 크기에 해당하는 석판을 각각 두 장, 세 장, 세 장씩 얻으면서 손실되는 영역의 넓이는 10으로 가장 작게 된다.
  15×10의 크기는 한 장이라도 넣을 경우 전체의 손실이 너무 커지기 때문에, 만들기를 포기한 것이다. 한편으로, 가장 넓이가 작은 돌판만으로 여러 장을 잘라 낸다고 해도 손실을 이보다 줄일 수 없다는 것은, 손으로 따져 보면 금방 알 수 있다.

돌판의 원래 크기와 우리가 원하는 돌판 크기들을 입력 받은 뒤, 가장 효율적으로 돌판을 자르는 방법을 계산하여 그때 손실되는 최소한의 돌판 면적의 합을 구하는 프로그램을 작성하시오. 어느 크기의 돌판을 얼마나 얻느냐가 아니라, 어떻게 자르든 손실을 줄이는 것이 목적이다.

입력

첫 줄에는 대리석 원판의 크기를 나타내는 W(가로 길이), H(세로 길이)가 들어있다. 다음 줄에는 우리가 원하는 크기의 개수 N이 있고, 그다음 N줄에는 그 크기들이 역시 가로, 세로 순으로 들어있다. 1≤ W, H ≤600이고 0 < N ≤ 200이다. 잘라야 하는 크기는 가로· 세로 모두 1 이상이고 원판의 크기 이하이다.

출력

정수 하나를 출력한다. 원판을 가장 현명하게 잘랐을 때 손실되는 면적의 최소값이다.

예제 입력 1

21 11
4
10 4
6 2
7 5
15 10

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjE2OTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMWRcdWQzMTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNlMFx1YjMwMFx1YzVkMCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjODcwXHVhYzAxXHVhYzAwXHVjNzc4IFx1YzYyNFx1YzEzOFx1YzkwMFx1Yzc0MCBcdWI2MTBcdWIyZTRcdWI5NzggXHVhYzc4XHVjNzkxXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjOTAwXHViZTQ0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVhYzAwXHViODVjIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzBcdWFjMDAgVzEmdGltZXM7SDEsIFcyJnRpbWVzO0gyLCAuLi4gV24mdGltZXM7SG5cdWM3NzggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWIzMDBcdWI5YWNcdWMxMWQgXHVjMTFkXHVkMzEwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWM3YTUgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cdWM1YmNcdWI5YzggXHVjODA0LCBcdWMxMzhcdWM5MDBcdWM3NzRcdWIyOTQgXHVjZWU0XHViMmU0XHViNzgwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWMxMWRcdWQzMTBcdWM3NDQgXHViYzFiXHVjNTU4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjNzc0XHVhYzgzXHVjNzQ0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzExZFx1ZDMxMFx1YjRlNFx1Yjg1YyBcdWNhYmNcdWFjMWNcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LiBcdWMxMWRcdWQzMTBcdWM3NDAgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzIxOCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHVhYzAwXHViODVjXHViMDk4IFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWM2NDRcdWM4MDRcdWQ3ODggXHVjNzk4XHViNzdjXHVjMTFjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWM3OTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Yzc5MVx1Yzc0MCBcdWMxMWRcdWQzMTBcdWI0ZTRcdWM3NDQgXHViZDk5XHVjNWVjXHVjMTFjIFx1ZDA3MCBcdWQzMTBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVjMTFkXHVkMzEwXHVjNWQwXHViMjk0IFx1Yzc3Y1x1YzgxNVx1ZDU1YyBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViYjM0XHViMmFjXHVhYzAwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1ZDY4Y1x1YzgwNFx1ZDU3NFx1YzExYyBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVkMDZjXHVhZTMwXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWIyZTRcdWMyZGMgXHViOWQwXHVkNTc0LCBBJnRpbWVzO0JcdWI3N2NcdWIyOTQgXHVkMDZjXHVhZTMwXHViODVjIFx1Yzc5OFx1Yjc5MFx1YjJlNFx1YmE3NCBcdWM3NzRcdWFjODNcdWM3NDQgQiZ0aW1lcztBXHViNzdjXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YzVkMCBcdWI5ZGVcdWNkOTRcdWM1YjQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWMxMWRcdWQzMTBcdWM1ZDBcdWMxMWMgXHVjNmQwXHVkNTU4XHViMjk0IFx1ZDA2Y1x1YWUzMFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYTc0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM3OThcdWI3N2MgXHViMGI4IFx1YjRhNCwgXHVjNWI0XHViMjkwIFx1ZDA2Y1x1YWUzMFx1Yjg1Y1x1YjNjNCBcdWNhYmNcdWFjMjQgXHVjMjE4IFx1YzVjNlx1YzViNCBcdWIwYThcdWFjOGMgXHViNDFjIFx1YmE3NFx1YjRlNFx1Yzc0MCBcdWJjODRcdWI4MjRcdWM5YzRcdWIyZTQuIFx1YzEzOFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWM2ZDBcdWQzMTBcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjIFx1Yzc5MFx1Yjk3NFx1YmE3NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMTkwXHVjMmU0XHVjNzQ0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHVjOTA0XHVjNzdjIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWM5YzAgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD48aW1nIHdpZHRoPVwiMjY4XCIgaGVpZ2h0PVwiMTQ2XCIgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDVcL3RqcnZrcy5QTkdcIiBcLz48XC9wPlxyXG48cD5cdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0XHVhYzAwIDIxXHVjNzc0XHVhY2UwIFx1YzEzOFx1Yjg1YyBcdWFlMzhcdWM3NzRcdWFjMDAgMTFcdWM3NzggXHVjZWU0XHViMmU0XHViNzgwIFx1YzExZFx1ZDMxMFx1Yzc0NCBcdWM2MDhcdWI4NWMgXHViNGU0XHVjNWI0IFx1YmNmNFx1Yzc5MC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzZiMFx1YjlhY1x1YzVkMFx1YWM4YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMTFkXHVkMzEwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWM4ODVcdWI5NThcdWFjMDAgMTAmdGltZXM7NCwgNiZ0aW1lczsyLCA3JnRpbWVzOzUsIFx1YWRmOFx1YjlhY1x1YWNlMCAxNSZ0aW1lczsxMFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1Yzc3NCBcdWFjYmRcdWM2YjAgXHVjMTFkXHVkMzEwXHVjNzQ0IFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Yzc5MFx1Yjk3NFx1YmE3NCwgXHVhYzAxIFx1ZDA2Y1x1YWUzMFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjMTFkXHVkMzEwXHVjNzQ0IFx1YWMwMVx1YWMwMSBcdWI0NTAgXHVjN2E1LCBcdWMxMzggXHVjN2E1LCBcdWMxMzggXHVjN2E1XHVjNTI5IFx1YzViYlx1YzczY1x1YmE3NFx1YzExYyBcdWMxOTBcdWMyZTRcdWI0MThcdWIyOTQgXHVjNjAxXHVjNWVkXHVjNzU4IFx1YjExM1x1Yzc3NFx1YjI5NCAxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVhYzhjIFx1YjQxY1x1YjJlNC48YnIgXC8+XHJcbiZuYnNwOyAxNSZ0aW1lczsxMFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHVkNTVjIFx1YzdhNVx1Yzc3NFx1Yjc3Y1x1YjNjNCBcdWIxMjNcdWM3NDQgXHVhY2JkXHVjNmIwIFx1YzgwNFx1Y2NiNFx1Yzc1OCBcdWMxOTBcdWMyZTRcdWM3NzQgXHViMTA4XHViYjM0IFx1Y2VlNFx1YzljMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjk3YyBcdWQzZWNcdWFlMzBcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQ1NWNcdWQzYjhcdWM3M2NcdWI4NWMsIFx1YWMwMFx1YzdhNSBcdWIxMTNcdWM3NzRcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YjNjY1x1ZDMxMFx1YjljY1x1YzczY1x1Yjg1YyBcdWM1ZWNcdWI3ZWMgXHVjN2E1XHVjNzQ0IFx1Yzc5OFx1Yjc3YyBcdWIwYjhcdWIyZTRcdWFjZTAgXHVkNTc0XHViM2M0IFx1YzE5MFx1YzJlNFx1Yzc0NCBcdWM3NzRcdWJjZjRcdWIyZTQgXHVjOTA0XHVjNzdjIFx1YzIxOCBcdWM1YzZcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwLCBcdWMxOTBcdWM3M2NcdWI4NWMgXHViNTMwXHVjODM4IFx1YmNmNFx1YmE3NCBcdWFlMDhcdWJjMjkgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHViM2NjXHVkMzEwXHVjNzU4IFx1YzZkMFx1Yjc5OCBcdWQwNmNcdWFlMzBcdWM2NDAgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWIzY2NcdWQzMTAgXHVkMDZjXHVhZTMwXHViNGU0XHVjNzQ0IFx1Yzc4NVx1YjgyNSBcdWJjMWJcdWM3NDAgXHViNGE0LCBcdWFjMDBcdWM3YTUgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzNjXHViODVjIFx1YjNjY1x1ZDMxMFx1Yzc0NCBcdWM3OTBcdWI5NzRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzVlYyBcdWFkZjhcdWI1NGMgXHVjMTkwXHVjMmU0XHViNDE4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWIzY2NcdWQzMTAgXHViYTc0XHVjODAxXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNWI0XHViMjkwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWIzY2NcdWQzMTBcdWM3NDQgXHVjNWJjXHViOWM4XHViMDk4IFx1YzViYlx1YjI5MFx1YjBkMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2MsIFx1YzViNFx1YjViYlx1YWM4YyBcdWM3OTBcdWI5NzRcdWI0ZTAgXHVjMTkwXHVjMmU0XHVjNzQ0IFx1YzkwNFx1Yzc3NFx1YjI5NCBcdWFjODNcdWM3NzQgXHViYWE5XHVjODAxXHVjNzc0XHViMmU0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjMwMFx1YjlhY1x1YzExZCBcdWM2ZDBcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBXKFx1YWMwMFx1Yjg1YyBcdWFlMzhcdWM3NzQpLCBIKFx1YzEzOFx1Yjg1YyBcdWFlMzhcdWM3NzQpXHVhYzAwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM3ODhcdWFjZTAsIFx1YWRmOFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOCBcdWQwNmNcdWFlMzBcdWI0ZTRcdWM3NzQgXHVjNWVkXHVjMmRjIFx1YWMwMFx1Yjg1YywgXHVjMTM4XHViODVjIFx1YzIxY1x1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIDEmbGU7IFcsIEggJmxlOzYwMFx1Yzc3NFx1YWNlMCAwICZsdDsgTiAmbGU7IDIwMFx1Yzc3NFx1YjJlNC4gXHVjNzk4XHViNzdjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWIyOTQgXHVhYzAwXHViODVjJm1pZGRvdDsgXHVjMTM4XHViODVjIFx1YmFhOFx1YjQ1MCAxIFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YWNlMCBcdWM2ZDBcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM2ZDBcdWQzMTBcdWM3NDQgXHVhYzAwXHVjN2E1IFx1ZDYwNFx1YmE4NVx1ZDU1OFx1YWM4YyBcdWM3OThcdWI3OTBcdWM3NDQgXHViNTRjIFx1YzE5MFx1YzJlNFx1YjQxOFx1YjI5NCBcdWJhNzRcdWM4MDFcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTY5MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBoaWRpYXMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhbW91cyBhbmNpZW50IEdyZWVrIHNjdWxwdG9yIFBoaWRpYXMgaXMgbWFraW5nIHByZXBhcmF0aW9ucyB0byBidWlsZCBhbm90aGVyIG1hcnZlbG91cyBtb251bWVudC4gRm9yIHRoaXMgcHVycG9zZSBoZSBuZWVkcyByZWN0YW5ndWxhciBtYXJibGUgcGxhdGVzIG9mIHNpemVzIFcxIEgxLCBXMiBIMiwgLi4uLCBXTiBITi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UmVjZW50bHksIFBoaWRpYXMgaGFzIHJlY2VpdmVkIGEgbGFyZ2UgcmVjdGFuZ3VsYXIgbWFyYmxlIHNsYWIuIEhlIHdhbnRzIHRvIGN1dCB0aGUgc2xhYiB0byBvYnRhaW4gcGxhdGVzIG9mIHRoZSBkZXNpcmVkIHNpemVzLiBBbnkgcGllY2Ugb2YgbWFyYmxlICh0aGUgc2xhYiBvciB0aGUgcGxhdGVzIGN1dCBmcm9tIGl0KSBjYW4gYmUgY3V0IGVpdGhlciBob3Jpem9udGFsbHkgb3IgdmVydGljYWxseSBpbnRvIHR3byByZWN0YW5ndWxhciBwbGF0ZXMgd2l0aCBpbnRlZ3JhbCB3aWR0aHMgYW5kIGhlaWdodHMsIGN1dHRpbmcgY29tcGxldGVseSB0aHJvdWdoIHRoYXQgcGllY2UuIFRoaXMgaXMgdGhlIG9ubHkgd2F5IHRvIGN1dCBwaWVjZXMgYW5kIHBpZWNlcyBjYW5ub3QgYmUgam9pbmVkIHRvZ2V0aGVyLiBTaW5jZSB0aGUgbWFyYmxlIGhhcyBhIHBhdHRlcm4gb24gaXQsIHRoZSBwbGF0ZXMgY2Fubm90IGJlIHJvdGF0ZWQ6IGlmIFBoaWRpYXMgY3V0cyBhIHBsYXRlIG9mIHNpemUgQSBCIHRoZW4gaXQgY2Fubm90IGJlIHVzZWQgYXMgYSBwbGF0ZSBvZiBzaXplIEIgQSB1bmxlc3MgQSBCLiBIZSBjYW4gbWFrZSB6ZXJvIG9yIG1vcmUgcGxhdGVzIG9mIGVhY2ggZGVzaXJlZCBzaXplLiBBIG1hcmJsZSBwbGF0ZSBpcyB3YXN0ZWQgaWYgaXQgaXMgbm90IG9mIGFueSBvZiB0aGUgZGVzaXJlZCBzaXplcyBhZnRlciBhbGwgY3V0cyBhcmUgY29tcGxldGVkLiBQaGlkaWFzIHdvbmRlcnMgaG93IHRvIGN1dCB0aGUgaW5pdGlhbCBzbGFiIHNvIHRoYXQgYXMgbGl0dGxlIG9mIGl0IGFzIHBvc3NpYmxlIHdpbGwgYmUgd2FzdGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BcyBhbiBleGFtcGxlLCBhc3N1bWUgdGhhdCBpbiB0aGUgZmlndXJlIGJlbG93IHRoZSB3aWR0aCBvZiB0aGUgb3JpZ2luYWwgc2xhYiBpcyAyMSBhbmQgdGhlIGhlaWdodCBvZiB0aGUgb3JpZ2luYWwgc2xhYiBpcyAxMSwgYW5kIHRoZSBkZXNpcmVkIHBsYXRlIHNpemVzIGFyZSAxMCA0LCA2IDIsIDcgNSwgYW5kIDE1IDEwLiBUaGUgbWluaW11bSBwb3NzaWJsZSBhcmVhIHdhc3RlZCBpcyAxMCwgYW5kIHRoZSBmaWd1cmUgc2hvd3Mgb25lIHNlcXVlbmNlIG9mIGN1dHMgd2l0aCB0b3RhbCB3YXN0ZSBhcmVhIG9mIHNpemUgMTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDVcL3RqcnZrcy5QTkdcIiBzdHlsZT1cImhlaWdodDoxNDZweDsgd2lkdGg6MjY4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgc2l6ZSBvZiB0aGUgb3JpZ2luYWwgc2xhYiBhbmQgdGhlIGRlc2lyZWQgcGxhdGUgc2l6ZXMsIGNhbGN1bGF0ZXMgdGhlIG1pbmltdW0gdG90YWwgYXJlYSBvZiB0aGUgb3JpZ2luYWwgc2xhYiB0aGF0IG11c3QgYmUgd2FzdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzOiBmaXJzdCBXLCB0aGUgd2lkdGggb2YgdGhlIG9yaWdpbmFsIHNsYWIsIGFuZCB0aGVuIEgsIHRoZSBoZWlnaHQgb2YgdGhlIG9yaWdpbmFsIHNsYWIuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBOOiB0aGUgbnVtYmVyIG9mIGRlc2lyZWQgcGxhdGUgc2l6ZXMuIFRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIHRoZSBkZXNpcmVkIHBsYXRlIHNpemVzLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VyczogZmlyc3QgdGhlIHdpZHRoIFdpIGFuZCB0aGVuIHRoZSBoZWlnaHQgSGkgb2YgdGhhdCBkZXNpcmVkIHBsYXRlIHNpemUgKDEgJmxlOyBpICZsZTsgTikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBpcyB0byBjb250YWluIG9uZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlcjogdGhlIG1pbmltdW0gdG90YWwgYXJlYSBvZiB0aGUgb3JpZ2luYWwgc2xhYiB0aGF0IG11c3QgYmUgd2FzdGVkLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2004 4번

  • 문제를 번역한 사람: author6