시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB1631007265.455%

문제

고대에 유명한 조각가인 오세준은 또다른 걸작을 만들기 위한 준비 작업을 하고 있다. 그래서 가로 세로 크기가 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
W3sicHJvYmxlbV9pZCI6IjE2OTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMWRcdWQzMTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNlMFx1YjMwMFx1YzVkMCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjODcwXHVhYzAxXHVhYzAwXHVjNzc4IFx1YzYyNFx1YzEzOFx1YzkwMFx1Yzc0MCBcdWI2MTBcdWIyZTRcdWI5NzggXHVhYzc4XHVjNzkxXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjOTAwXHViZTQ0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVhYzAwXHViODVjIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzBcdWFjMDAgVzxzdWI+MTxcL3N1Yj4mdGltZXM7SDxzdWI+MTxcL3N1Yj4sIFc8c3ViPjI8XC9zdWI+JnRpbWVzO0g8c3ViPjI8XC9zdWI+LCAuLi4gVzxzdWI+bjxcL3N1Yj4mdGltZXM7SDxzdWI+bjxcL3N1Yj5cdWM3NzggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWIzMDBcdWI5YWNcdWMxMWQgXHVjMTFkXHVkMzEwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWM3YTUgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWJjXHViOWM4IFx1YzgwNCwgXHVjMTM4XHVjOTAwXHVjNzc0XHViMjk0IFx1Y2VlNFx1YjJlNFx1Yjc4MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjMTFkXHVkMzEwXHVjNzQ0IFx1YmMxYlx1YzU1OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1Yzc3NFx1YWM4M1x1Yzc0NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVkMDZjXHVhZTMwXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWMxMWRcdWQzMTBcdWI0ZTRcdWI4NWMgXHVjYWJjXHVhYzFjXHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1Y1x1YjJlNC4gXHVjMTFkXHVkMzEwXHVjNzQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM4MTVcdWMyMTggXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YWMwMFx1Yjg1Y1x1YjA5OCBcdWMxMzhcdWI4NWNcdWI4NWMgXHVjNjQ0XHVjODA0XHVkNzg4IFx1Yzc5OFx1Yjc3Y1x1YzExYyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWMgXHVjNzkwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM3OTFcdWM3NDAgXHVjMTFkXHVkMzEwXHViNGU0XHVjNzQ0IFx1YmQ5OVx1YzVlY1x1YzExYyBcdWQwNzAgXHVkMzEwXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1YzExZFx1ZDMxMFx1YzVkMFx1YjI5NCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YmIzNFx1YjJhY1x1YWMwMCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ2OGNcdWM4MDRcdWQ1NzRcdWMxMWMgXHVjNmQwXHVkNTU4XHViMjk0IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC4gXHViMmU0XHVjMmRjIFx1YjlkMFx1ZDU3NCwgQSZ0aW1lcztCXHViNzdjXHViMjk0IFx1ZDA2Y1x1YWUzMFx1Yjg1YyBcdWM3OThcdWI3OTBcdWIyZTRcdWJhNzQgXHVjNzc0XHVhYzgzXHVjNzQ0IEImdGltZXM7QVx1Yjc3Y1x1YjI5NCBcdWQwNmNcdWFlMzBcdWM1ZDAgXHViOWRlXHVjZDk0XHVjNWI0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjMTFkXHVkMzEwXHVjNWQwXHVjMTFjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YmE3NFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjNzk4XHViNzdjIFx1YjBiOCBcdWI0YTQsIFx1YzViNFx1YjI5MCBcdWQwNmNcdWFlMzBcdWI4NWNcdWIzYzQgXHVjYWJjXHVhYzI0IFx1YzIxOCBcdWM1YzZcdWM1YjQgXHViMGE4XHVhYzhjIFx1YjQxYyBcdWJhNzRcdWI0ZTRcdWM3NDAgXHViYzg0XHViODI0XHVjOWM0XHViMmU0LiBcdWMxMzhcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNmQwXHVkMzEwXHVjNzQ0IFx1YzViNFx1YjViYlx1YWM4YyBcdWM3OTBcdWI5NzRcdWJhNzQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YzE5MFx1YzJlNFx1Yzc0NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YzkwNFx1Yzc3YyBcdWMyMTggXHVjNzg4XHVjNzQ0XHVjOWMwIFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMjVmNWRjNTItZTdiMS00NDc3LWIyOGItNjZjYjIyOWIzNmNmXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNjNweDsgaGVpZ2h0OiAxNDFweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViODVjIFx1YWUzOFx1Yzc3NFx1YWMwMCAyMVx1Yzc3NFx1YWNlMCBcdWMxMzhcdWI4NWMgXHVhZTM4XHVjNzc0XHVhYzAwIDExXHVjNzc4IFx1Y2VlNFx1YjJlNFx1Yjc4MCBcdWMxMWRcdWQzMTBcdWM3NDQgXHVjNjA4XHViODVjIFx1YjRlNFx1YzViNCBcdWJjZjRcdWM3OTAuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM2YjBcdWI5YWNcdWM1ZDBcdWFjOGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzExZFx1ZDMxMCBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODg1XHViOTU4XHVhYzAwIDEwJnRpbWVzOzQsIDYmdGltZXM7MiwgNyZ0aW1lczs1LCBcdWFkZjhcdWI5YWNcdWFjZTAgMTUmdGltZXM7MTBcdWM3NzRcdWI3N2NcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNzkwLiBcdWM3NzQgXHVhY2JkXHVjNmIwIFx1YzExZFx1ZDMxMFx1Yzc0NCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3OTBcdWI5NzRcdWJhNzQsIFx1YWMwMSBcdWQwNmNcdWFlMzBcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YzExZFx1ZDMxMFx1Yzc0NCBcdWFjMDFcdWFjMDEgXHViNDUwIFx1YzdhNSwgXHVjMTM4IFx1YzdhNSwgXHVjMTM4IFx1YzdhNVx1YzUyOSBcdWM1YmJcdWM3M2NcdWJhNzRcdWMxMWMgXHVjMTkwXHVjMmU0XHViNDE4XHViMjk0IFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWIxMTNcdWM3NzRcdWIyOTQgMTBcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjE1JnRpbWVzOzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWQ1NWMgXHVjN2E1XHVjNzc0XHViNzdjXHViM2M0IFx1YjEyM1x1Yzc0NCBcdWFjYmRcdWM2YjAgXHVjODA0XHVjY2I0XHVjNzU4IFx1YzE5MFx1YzJlNFx1Yzc3NCBcdWIxMDhcdWJiMzQgXHVjZWU0XHVjOWMwXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViOWNjXHViNGU0XHVhZTMwXHViOTdjIFx1ZDNlY1x1YWUzMFx1ZDU1YyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1Y1x1ZDNiOFx1YzczY1x1Yjg1YywgXHVhYzAwXHVjN2E1IFx1YjExM1x1Yzc3NFx1YWMwMCBcdWM3OTFcdWM3NDAgXHViM2NjXHVkMzEwXHViOWNjXHVjNzNjXHViODVjIFx1YzVlY1x1YjdlYyBcdWM3YTVcdWM3NDQgXHVjNzk4XHViNzdjIFx1YjBiOFx1YjJlNFx1YWNlMCBcdWQ1NzRcdWIzYzQgXHVjMTkwXHVjMmU0XHVjNzQ0IFx1Yzc3NFx1YmNmNFx1YjJlNCBcdWM5MDRcdWM3N2MgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDAsIFx1YzE5MFx1YzczY1x1Yjg1YyBcdWI1MzBcdWM4MzggXHViY2Y0XHViYTc0IFx1YWUwOFx1YmMyOSBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2NjXHVkMzEwXHVjNzU4IFx1YzZkMFx1Yjc5OCBcdWQwNmNcdWFlMzBcdWM2NDAgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWIzY2NcdWQzMTAgXHVkMDZjXHVhZTMwXHViNGU0XHVjNzQ0IFx1Yzc4NVx1YjgyNSBcdWJjMWJcdWM3NDAgXHViNGE0LCBcdWFjMDBcdWM3YTUgXHVkNmE4XHVjNzI4XHVjODAxXHVjNzNjXHViODVjIFx1YjNjY1x1ZDMxMFx1Yzc0NCBcdWM3OTBcdWI5NzRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzVlYyBcdWFkZjhcdWI1NGMgXHVjMTkwXHVjMmU0XHViNDE4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWIzY2NcdWQzMTAgXHViYTc0XHVjODAxXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNWI0XHViMjkwIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWIzY2NcdWQzMTBcdWM3NDQgXHVjNWJjXHViOWM4XHViMDk4IFx1YzViYlx1YjI5MFx1YjBkMFx1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2MsIFx1YzViNFx1YjViYlx1YWM4YyBcdWM3OTBcdWI5NzRcdWI0ZTAgXHVjMTkwXHVjMmU0XHVjNzQ0IFx1YzkwNFx1Yzc3NFx1YjI5NCBcdWFjODNcdWM3NzQgXHViYWE5XHVjODAxXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzMDBcdWI5YWNcdWMxMWQgXHVjNmQwXHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgVyhcdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0KSwgSChcdWMxMzhcdWI4NWMgXHVhZTM4XHVjNzc0KVx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFkZjhcdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkZjggXHVkMDZjXHVhZTMwXHViNGU0XHVjNzc0IFx1YzVlZFx1YzJkYyBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YyBcdWMyMWNcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LiAxICZsZTsgVywgSCAmbGU7IDYwMFx1Yzc3NFx1YWNlMCAwICZsdDsgTiAmbGU7IDIwMFx1Yzc3NFx1YjJlNC4gXHVjNzk4XHViNzdjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQwNmNcdWFlMzBcdWIyOTQgXHVhYzAwXHViODVjJm1pZGRvdDsgXHVjMTM4XHViODVjIFx1YmFhOFx1YjQ1MCAxIFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YWNlMCBcdWM2ZDBcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MTVcdWMyMTggXHVkNTU4XHViMDk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNmQwXHVkMzEwXHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWQ2MDRcdWJhODVcdWQ1NThcdWFjOGMgXHVjNzk4XHViNzkwXHVjNzQ0IFx1YjU0YyBcdWMxOTBcdWMyZTRcdWI0MThcdWIyOTQgXHViYTc0XHVjODAxXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxNjkxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGhpZGlhcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFtb3VzIGFuY2llbnQgR3JlZWsgc2N1bHB0b3IgUGhpZGlhcyBpcyBtYWtpbmcgcHJlcGFyYXRpb25zIHRvIGJ1aWxkIGFub3RoZXIgbWFydmVsb3VzIG1vbnVtZW50LiBGb3IgdGhpcyBwdXJwb3NlIGhlIG5lZWRzIHJlY3Rhbmd1bGFyIG1hcmJsZSBwbGF0ZXMgb2Ygc2l6ZXMgVzxzdWI+MTxcL3N1Yj4mbmJzcDsmdGltZXM7IEg8c3ViPjE8XC9zdWI+LCBXPHN1Yj4yPFwvc3ViPiZuYnNwOyZ0aW1lczsgSDxzdWI+MjxcL3N1Yj4sIC4uLiBXPHN1Yj5OPFwvc3ViPiZuYnNwOyZ0aW1lczsgSDxzdWI+TjxcL3N1Yj4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlJlY2VudGx5LCBQaGlkaWFzIGhhcyByZWNlaXZlZCBhIGxhcmdlIHJlY3Rhbmd1bGFyIG1hcmJsZSBzbGFiLiBIZSB3YW50cyB0byBjdXQgdGhlIHNsYWIgdG8gb2J0YWluIHBsYXRlcyBvZiB0aGUgZGVzaXJlZCBzaXplcy4gQW55IHBpZWNlIG9mIG1hcmJsZSAodGhlIHNsYWIgb3IgdGhlIHBsYXRlcyBjdXQgZnJvbSBpdCkgY2FuIGJlIGN1dCBlaXRoZXIgaG9yaXpvbnRhbGx5IG9yIHZlcnRpY2FsbHkgaW50byB0d28gcmVjdGFuZ3VsYXIgcGxhdGVzIHdpdGggaW50ZWdyYWwgd2lkdGhzIGFuZCBoZWlnaHRzLCBjdXR0aW5nIGNvbXBsZXRlbHkgdGhyb3VnaCB0aGF0IHBpZWNlLiBUaGlzIGlzIHRoZSBvbmx5IHdheSB0byBjdXQgcGllY2VzIGFuZCBwaWVjZXMgY2Fubm90IGJlIGpvaW5lZCB0b2dldGhlci4gU2luY2UgdGhlIG1hcmJsZSBoYXMgYSBwYXR0ZXJuIG9uIGl0LCB0aGUgcGxhdGVzIGNhbm5vdCBiZSByb3RhdGVkOiBpZiBQaGlkaWFzIGN1dHMgYSBwbGF0ZSBvZiBzaXplIEEgJnRpbWVzOyBCIHRoZW4gaXQgY2Fubm90IGJlIHVzZWQgYXMgYSBwbGF0ZSBvZiBzaXplIEImbmJzcDsmdGltZXM7IEEgdW5sZXNzIEEmbmJzcDsmdGltZXM7IEIuIEhlIGNhbiBtYWtlIHplcm8gb3IgbW9yZSBwbGF0ZXMgb2YgZWFjaCBkZXNpcmVkIHNpemUuIEEgbWFyYmxlIHBsYXRlIGlzIHdhc3RlZCBpZiBpdCBpcyBub3Qgb2YgYW55IG9mIHRoZSBkZXNpcmVkIHNpemVzIGFmdGVyIGFsbCBjdXRzIGFyZSBjb21wbGV0ZWQuIFBoaWRpYXMgd29uZGVycyBob3cgdG8gY3V0IHRoZSBpbml0aWFsIHNsYWIgc28gdGhhdCBhcyBsaXR0bGUgb2YgaXQgYXMgcG9zc2libGUgd2lsbCBiZSB3YXN0ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzIGFuIGV4YW1wbGUsIGFzc3VtZSB0aGF0IGluIHRoZSBmaWd1cmUgYmVsb3cgdGhlIHdpZHRoIG9mIHRoZSBvcmlnaW5hbCBzbGFiIGlzIDIxIGFuZCB0aGUgaGVpZ2h0IG9mIHRoZSBvcmlnaW5hbCBzbGFiIGlzIDExLCBhbmQgdGhlIGRlc2lyZWQgcGxhdGUgc2l6ZXMgYXJlIDEwJm5ic3A7JnRpbWVzOyA0LCA2Jm5ic3A7JnRpbWVzOyAyLCA3Jm5ic3A7JnRpbWVzOyA1LCBhbmQgMTUmbmJzcDsmdGltZXM7IDEwLiBUaGUgbWluaW11bSBwb3NzaWJsZSBhcmVhIHdhc3RlZCBpcyAxMCwgYW5kIHRoZSBmaWd1cmUgc2hvd3Mgb25lIHNlcXVlbmNlIG9mIGN1dHMgd2l0aCB0b3RhbCB3YXN0ZSBhcmVhIG9mIHNpemUgMTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMjVmNWRjNTItZTdiMS00NDc3LWIyOGItNjZjYjIyOWIzNmNmXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNjNweDsgaGVpZ2h0OiAxNDFweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgc2l6ZSBvZiB0aGUgb3JpZ2luYWwgc2xhYiBhbmQgdGhlIGRlc2lyZWQgcGxhdGUgc2l6ZXMsIGNhbGN1bGF0ZXMgdGhlIG1pbmltdW0gdG90YWwgYXJlYSBvZiB0aGUgb3JpZ2luYWwgc2xhYiB0aGF0IG11c3QgYmUgd2FzdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzOiBmaXJzdCBXLCB0aGUgd2lkdGggb2YgdGhlIG9yaWdpbmFsIHNsYWIsIGFuZCB0aGVuIEgsIHRoZSBoZWlnaHQgb2YgdGhlIG9yaWdpbmFsIHNsYWIuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBOOiB0aGUgbnVtYmVyIG9mIGRlc2lyZWQgcGxhdGUgc2l6ZXMuIFRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIHRoZSBkZXNpcmVkIHBsYXRlIHNpemVzLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VyczogZmlyc3QgdGhlIHdpZHRoIFdpIGFuZCB0aGVuIHRoZSBoZWlnaHQgSGkgb2YgdGhhdCBkZXNpcmVkIHBsYXRlIHNpemUgKDEgJmxlOyBpICZsZTsgTikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBpcyB0byBjb250YWluIG9uZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlcjogdGhlIG1pbmltdW0gdG90YWwgYXJlYSBvZiB0aGUgb3JpZ2luYWwgc2xhYiB0aGF0IG11c3QgYmUgd2FzdGVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IFcgJmxlOyA2MDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IEggJmxlOyA2MDA8XC9saT5cclxuXHQ8bGk+MCAmbHQ7IE4gJmxlOyAyMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFc8c3ViPmk8XC9zdWI+ICZsZTsgVzxcL2xpPlxyXG5cdDxsaT4xICZsZTsgSDxzdWI+aTxcL3N1Yj4gJmxlOyBIPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2004 > Day 2 4번