시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 26 17 37.778%

문제

재현이는 BOJ에서 가장 아름다운 정원을 소유하고 있는 사람으로, 정원에 n개의 꽃을 심어놓았다. 모든 꽃들이 화사하게 핀 여름날. 재현이는 아름다운 꽃들을 보고 있으니 갑자기 대한민국의 경제가 걱정되기 시작해서, 두명의 정원사 박승원과 신승원을 고용해서 실업률을 낮추고 경제를 활성화시키려고 한다.

정원은 가로가 l미터, 세로가 w미터인 직사각형 모양이며, 가로 세로가 1미터인 l*w 개의 정사각형 칸으로 분할되어 있다. 정원은 x축과 y축에 평행하며, 정원 내부에 있는 모든 정사각형 칸은 1 ≤ x ≤ l, 1 ≤ y ≤ w인 정수 좌표 (x,y) 로 표현할 수 있다.

만약 재현이가 (l1,w1), (l1,w2), (l2,w1), (l2,w2)를 모서리로 갖는 직사각형을 골랐다면 이 영역은 1 ≤ l1 ≤ l2 ≤ l, 1 ≤ w1 ≤ w2 ≤ w 를 만족하는 모든 칸 (x,y)를 포함하며 이 영역의 둘레는 2 · (l2 − l1 + 1) + 2 · (w2 − w1 + 1) 이다.

재현이가 하고 싶은 일은 이 정원에 두개의 겹치지 않는 직사각형 모양의 울타리를 치고, 그 직사각형 영역 안에 들어있는 장미의 개수를 모두 동일하게 k개로 유지하는 것이다.

재현이는 이렇게 생긴 두개의 구역을 각각 박승원과 신승원에게 할당할 계획이다. 하지만, 애석하게도 울타리는 수입 제품이기 때문에 경제를 살리는데 아무런 도움이 안된다. 때문에 재현이는 울타리를 치는 영역의 둘레를 최소화해서 내수 시장을 활성화시킬 계획이다.

정원의 크기와 장미들의 위치, 그리고 정원사에게 할당하고 싶은 장미의 수를 입력받아, 최소한의 길이로 울타리를 치면서 장미도 지정해 준 대로 들어있는 두 영역을 구하는 프로그램을 작성하시오.

두 영역은 서로 겹치면 안되며, 영역 내부에 정확히 k그루의 장미가 있어야 한다. 또한, 두 울타리가 겹치는 부분에는 울타리를 두번 설치해준다.

입력

첫 번째 줄에는 정원의 길이와 폭인 l,w가 주어진다. (1 ≤ l,w ≤ 250)

두 번째 줄에는 전체 장미의 수 n, 두 승원이가 할당받을 장미의 수 k가 주어진다. (2 ≤ n ≤ 5000 , 1 ≤ k ≤ n/2)

이후 i개의 줄에 i번째 장미가 있는 칸을 의미하는 두 정수 li, wi (1 ≤ li ≤ l, 1 ≤ wi ≤ w) 가 주어진다.

출력

둘레의 합이 최소인 두 영역을 구한 뒤, 두 영역의 둘레 길이의 합을 구한다. 만약 그러한 영역을 구할 수 없었다면 NO를 출력한다.

예제 입력 1

6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1

예제 출력 1

22

힌트

W3sicHJvYmxlbV9pZCI6IjU0ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWM2ZDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBCT0pcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWM4MTVcdWM2ZDBcdWM3NDQgXHVjMThjXHVjNzIwXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3M2NcdWI4NWMsIFx1YzgxNVx1YzZkMFx1YzVkMCBuXHVhYzFjXHVjNzU4IFx1YWY0M1x1Yzc0NCBcdWMyZWNcdWM1YjRcdWIxOTNcdWM1NThcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFmNDNcdWI0ZTRcdWM3NzQgXHVkNjU0XHVjMGFjXHVkNTU4XHVhYzhjIFx1ZDU0MCBcdWM1ZWNcdWI5ODRcdWIwYTAuIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHVhZjQzXHViNGU0XHVjNzQ0IFx1YmNmNFx1YWNlMCBcdWM3ODhcdWM3M2NcdWIyYzggXHVhYzExXHVjNzkwXHVhZTMwIFx1YjMwMFx1ZDU1Y1x1YmJmY1x1YWQ2ZFx1Yzc1OCBcdWFjYmRcdWM4MWNcdWFjMDAgXHVhYzcxXHVjODE1XHViNDE4XHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYywgXHViNDUwXHViYTg1XHVjNzU4IFx1YzgxNVx1YzZkMFx1YzBhYyBcdWJjMTVcdWMyYjlcdWM2ZDBcdWFjZmMgXHVjMmUwXHVjMmI5XHVjNmQwXHVjNzQ0IFx1YWNlMFx1YzZhOVx1ZDU3NFx1YzExYyBcdWMyZTRcdWM1YzVcdWI5NjBcdWM3NDQgXHViMGFlXHVjZDk0XHVhY2UwIFx1YWNiZFx1YzgxY1x1Yjk3YyBcdWQ2NWNcdWMxMzFcdWQ2NTRcdWMyZGNcdWQwYTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM2ZDBcdWM3NDAgXHVhYzAwXHViODVjXHVhYzAwIGxcdWJiZjhcdWQxMzAsIFx1YzEzOFx1Yjg1Y1x1YWMwMCB3XHViYmY4XHVkMTMwXHVjNzc4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NzRcdWJhNzAsIFx1YWMwMFx1Yjg1YyBcdWMxMzhcdWI4NWNcdWFjMDAgMVx1YmJmOFx1ZDEzMFx1Yzc3OCBsKncgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWNlNzhcdWM3M2NcdWI4NWMgXHViZDg0XHVkNTYwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjODE1XHVjNmQwXHVjNzQwIHhcdWNkOTVcdWFjZmMgeVx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWJhNzAsIFx1YzgxNVx1YzZkMCBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjZTc4XHVjNzQwIDEgJmxlOyB4ICZsZTsgbCwgMSAmbGU7IHkgJmxlOyB3XHVjNzc4IFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWMgKHgseSkgXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVjN2FjXHVkNjA0XHVjNzc0XHVhYzAwIChsPHN1Yj4xPFwvc3ViPix3PHN1Yj4xPFwvc3ViPiksIChsPHN1Yj4xPFwvc3ViPix3PHN1Yj4yPFwvc3ViPiksIChsPHN1Yj4yPFwvc3ViPix3PHN1Yj4xPFwvc3ViPiksIChsPHN1Yj4yPFwvc3ViPix3PHN1Yj4yPFwvc3ViPilcdWI5N2MgXHViYWE4XHVjMTFjXHViOWFjXHViODVjIFx1YWMxNlx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhY2U4XHViNzkwXHViMmU0XHViYTc0IFx1Yzc3NCBcdWM2MDFcdWM1ZWRcdWM3NDAgMSAmbGU7IGw8c3ViPjE8XC9zdWI+ICZsZTsgbDxzdWI+MjxcL3N1Yj4gJmxlOyBsLCAxICZsZTsgdzxzdWI+MTxcL3N1Yj4gJmxlOyB3PHN1Yj4yPFwvc3ViPiAmbGU7IHcgXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjZTc4ICh4LHkpXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YmE3MCBcdWM3NzQgXHVjNjAxXHVjNWVkXHVjNzU4IFx1YjQ1OFx1YjgwOFx1YjI5NCAyICZtaWRkb3Q7IChsPHN1Yj4yPFwvc3ViPiAmbWludXM7IGw8c3ViPjE8XC9zdWI+ICsgMSkgKyAyICZtaWRkb3Q7ICh3PHN1Yj4yPFwvc3ViPiAmbWludXM7IHc8c3ViPjE8XC9zdWI+ICsgMSkgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3YWNcdWQ2MDRcdWM3NzRcdWFjMDAgXHVkNTU4XHVhY2UwIFx1YzJmNlx1Yzc0MCBcdWM3N2NcdWM3NDAgXHVjNzc0IFx1YzgxNVx1YzZkMFx1YzVkMCBcdWI0NTBcdWFjMWNcdWM3NTggXHVhY2I5XHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWNlNThcdWFjZTAsIFx1YWRmOCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNjAxXHVjNWVkIFx1YzU0OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjN2E1XHViYmY4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViM2Q5XHVjNzdjXHVkNTU4XHVhYzhjIGtcdWFjMWNcdWI4NWMgXHVjNzIwXHVjOWMwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMwZGRcdWFlMzQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWFjMDFcdWFjMDEgXHViYzE1XHVjMmI5XHVjNmQwXHVhY2ZjIFx1YzJlMFx1YzJiOVx1YzZkMFx1YzVkMFx1YWM4YyBcdWQ1NjBcdWIyZjlcdWQ1NjAgXHVhY2M0XHVkNjhkXHVjNzc0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzU2MFx1YzExZFx1ZDU1OFx1YWM4Y1x1YjNjNCBcdWM2YjhcdWQwYzBcdWI5YWNcdWIyOTQgXHVjMjE4XHVjNzg1IFx1YzgxY1x1ZDQ4OFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhY2JkXHVjODFjXHViOTdjIFx1YzBiNFx1YjlhY1x1YjI5NFx1YjM3MCBcdWM1NDRcdWJiMzRcdWI3ZjAgXHViM2M0XHVjNmMwXHVjNzc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gXHViNTRjXHViYjM4XHVjNWQwIFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHVjZTU4XHViMjk0IFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWI0NThcdWI4MDhcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTc0XHVjMTFjIFx1YjBiNFx1YzIxOCBcdWMyZGNcdWM3YTVcdWM3NDQgXHVkNjVjXHVjMTMxXHVkNjU0XHVjMmRjXHVkMGFjIFx1YWNjNFx1ZDY4ZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjNmQwXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWM3YTVcdWJiZjhcdWI0ZTRcdWM3NTggXHVjNzA0XHVjZTU4LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjODE1XHVjNmQwXHVjMGFjXHVjNWQwXHVhYzhjIFx1ZDU2MFx1YjJmOVx1ZDU1OFx1YWNlMCBcdWMyZjZcdWM3NDAgXHVjN2E1XHViYmY4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM1NDQsIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI4NWMgXHVjNmI4XHVkMGMwXHViOWFjXHViOTdjIFx1Y2U1OFx1YmE3NFx1YzExYyBcdWM3YTVcdWJiZjhcdWIzYzQgXHVjOWMwXHVjODE1XHVkNTc0IFx1YzkwMCBcdWIzMDBcdWI4NWMgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YjQ1MCBcdWM2MDFcdWM1ZWRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWM2MDFcdWM1ZWRcdWM3NDAgXHVjMTFjXHViODVjIFx1YWNiOVx1Y2U1OFx1YmE3NCBcdWM1NDhcdWI0MThcdWJhNzAsIFx1YzYwMVx1YzVlZCBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjODE1XHVkNjU1XHVkNzg4IGtcdWFkZjhcdWI4ZThcdWM3NTggXHVjN2E1XHViYmY4XHVhYzAwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHViNDUwIFx1YzZiOFx1ZDBjMFx1YjlhY1x1YWMwMCBcdWFjYjlcdWNlNThcdWIyOTQgXHViZDgwXHViZDg0XHVjNWQwXHViMjk0IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWI0NTBcdWJjODggXHVjMTI0XHVjZTU4XHVkNTc0XHVjOTAwXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODE1XHVjNmQwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWQzZWRcdWM3NzggbCx3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBsLHcgJmxlOyAyNTApPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgwNFx1Y2NiNCBcdWM3YTVcdWJiZjhcdWM3NTggXHVjMjE4IG4sIFx1YjQ1MCBcdWMyYjlcdWM2ZDBcdWM3NzRcdWFjMDAgXHVkNTYwXHViMmY5XHViYzFiXHVjNzQ0IFx1YzdhNVx1YmJmOFx1Yzc1OCBcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgbiAmbGU7IDUwMDAgLCAxICZsZTsgayAmbGU7IG5cLzIpPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBpXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBpXHViYzg4XHVjOWY4IFx1YzdhNVx1YmJmOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IGw8c3ViPmk8XC9zdWI+LCB3PHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgbCwgMSAmbGU7IHc8c3ViPmk8XC9zdWI+ICZsZTsgdykgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI0NThcdWI4MDhcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1Yzc3OCBcdWI0NTAgXHVjNjAxXHVjNWVkXHVjNzQ0IFx1YWQ2Y1x1ZDU1YyBcdWI0YTQsIFx1YjQ1MCBcdWM2MDFcdWM1ZWRcdWM3NTggXHViNDU4XHViODA4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzYwMVx1YzVlZFx1Yzc0NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YzVjOFx1YjJlNFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzU0ODRcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTkzcHg7IHdpZHRoOjIwOXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NDg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2FyZGVuIiwiZGVzY3JpcHRpb24iOiI8cD5CeXRlbWFuIG93bnMgdGhlIG1vc3QgYmVhdXRpZnVsIGdhcmRlbiBpbiBCeXRldG93bi4gSGUgcGxhbnRlZCBuIHJvc2VzIGluIGhpcyBnYXJkZW4uIFN1bW1lciBoYXMgY29tZSBhbmQgdGhlIGZsb3dlcnMgaGF2ZSBncm93biBiaWcgYW5kIGJlYXV0aWZ1bC4gQnl0ZW1hbiBoYXMgcmVhbGl6ZWQgdGhhdCBoZSBpcyBub3QgYWJsZSB0byB0YWtlIGNhcmUgb2YgYWxsIHRoZSByb3NlcyBvbiBoaXMgb3duLiBIZSBoYXMgZGVjaWRlZCB0byBlbXBsb3kgdHdvIGdhcmRlbmVycyB0byBoZWxwIGhpbS4gSGUgd2FudHMgdG8gc2VsZWN0IHR3byByZWN0YW5ndWxhciBhcmVhcywgc28gdGhhdCBlYWNoIG9mIHRoZSBnYXJkZW5lcnMgd2lsbCB0YWtlIGNhcmUgb2YgdGhlIHJvc2VzIGluc2lkZSBvbmUgYXJlYS4gVGhlIGFyZWFzIHNob3VsZCBiZSBkaXNqb2ludCBhbmQgZWFjaCBzaG91bGQgY29udGFpbiBleGFjdGx5IGsgcm9zZXMuPFwvcD5cclxuXHJcbjxwPkJ5dGVtYW4gd2FudHMgdG8gbWFrZSBhIGZlbmNlIHN1cnJvdW5kaW5nIHRoZSByZWN0YW5ndWxhciBhcmVhcywgYnV0IGhlIGlzIHNob3J0IG9mIG1vbmV5LCBzbyBoZSB3YW50cyB0byB1c2UgYXMgbGl0dGxlIGZlbmNlIGFzIHBvc3NpYmxlLiBZb3VyIHRhc2sgaXMgdG8gaGVscCBCeXRlbWFuIHNlbGVjdCB0aGUgdHdvIHJlY3Rhbmd1bGFyIGFyZWFzLjxcL3A+XHJcblxyXG48cD5UaGUgZ2FyZGVuIGZvcm1zIGEgcmVjdGFuZ2xlIGwgbWV0ZXJzIGxvbmcgYW5kIHcgbWV0ZXJzIHdpZGUuIEl0IGlzIGRpdmlkZWQgaW50byBsJm1pZGRvdDt3IHNxdWFyZXMgb2Ygc2l6ZSAxIG1ldGVyICZ0aW1lczsgMSBtZXRlciBlYWNoLiBXZSBmaXggYSBjb29yZGluYXRlIHN5c3RlbSB3aXRoIGF4ZXMgcGFyYWxsZWwgdG8gdGhlIHNpZGVzIG9mIHRoZSBnYXJkZW4uIEFsbCBzcXVhcmVzIGhhdmUgaW50ZWdlciBjb29yZGluYXRlcyAoeCx5KSBzYXRpc2Z5aW5nIDEgJmxlOyB4ICZsZTsgbCwgMSAmbGU7IHkgJmxlOyB3LiBFYWNoIHNxdWFyZSBtYXkgY29udGFpbiBhbnkgbnVtYmVyIG9mIHJvc2VzLjxcL3A+XHJcblxyXG48cD5UaGUgcmVjdGFuZ3VsYXIgYXJlYXMsIHdoaWNoIG11c3QgYmUgc2VsZWN0ZWQsIHNob3VsZCBoYXZlIHRoZWlyIHNpZGVzIHBhcmFsbGVsIHRvIHRoZSBzaWRlcyBvZiB0aGUgZ2FyZGVuIGFuZCB0aGUgc3F1YXJlcyBpbiB0aGVpciBjb3JuZXJzIHNob3VsZCBoYXZlIGludGVnZXIgY29vcmRpbmF0ZXMuIEZvciAxICZsZTsgbDxzdWI+MTxcL3N1Yj4gJmxlOyBsPHN1Yj4yPFwvc3ViPiAmbGU7IGwgYW5kIDEgJmxlOyB3PHN1Yj4xPFwvc3ViPiAmbGU7IHc8c3ViPjI8XC9zdWI+ICZsZTsgdywgYSByZWN0YW5ndWxhciBhcmVhIHdpdGggY29ybmVycyAobDxzdWI+MTxcL3N1Yj4sdzxzdWI+MTxcL3N1Yj4pLCAobDxzdWI+MTxcL3N1Yj4sdzxzdWI+MjxcL3N1Yj4pLCAobDxzdWI+MjxcL3N1Yj4sdzxzdWI+MTxcL3N1Yj4pIGFuZCAobDxzdWI+MjxcL3N1Yj4sdzxzdWI+MjxcL3N1Yj4pOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmNvbnRhaW5zIGFsbCB0aGUgc3F1YXJlcyB3aXRoIGNvb3JkaW5hdGVzICh4LHkpIHNhdGlzZnlpbmcgbDxzdWI+MTxcL3N1Yj4gJmxlOyB4ICZsZTsgbDxzdWI+MjxcL3N1Yj4gYW5kIHc8c3ViPjE8XC9zdWI+ICZsZTsgeSAmbGU7IHc8c3ViPjI8XC9zdWI+LCBhbmQ8XC9saT5cclxuXHQ8bGk+aGFzIHBlcmltZXRlciAyICZtaWRkb3Q7IChsPHN1Yj4yPFwvc3ViPiAmbWludXM7IGw8c3ViPjE8XC9zdWI+ICsgMSkgKyAyICZtaWRkb3Q7ICh3PHN1Yj4yPFwvc3ViPiAmbWludXM7IHc8c3ViPjE8XC9zdWI+ICsgMSkuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIHR3byByZWN0YW5ndWxhciBhcmVhcyBtdXN0IGJlIGRpc2pvaW50LCB0aGF0IGlzIHRoZXkgY2Fubm90IGNvbnRhaW4gYSBjb21tb24gc3F1YXJlLiBFdmVuIGlmIHRoZXkgaGF2ZSBhIGNvbW1vbiBzaWRlLCBvciBwYXJ0IG9mIGl0LCB0aGV5IG11c3QgYmUgc3Vycm91bmRlZCBieSBzZXBhcmF0ZSBmZW5jZXMuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSwgdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgZ2FyZGVuLCB0aGUgbnVtYmVyIG9mIHJvc2VzIGluIHRoZSBnYXJkZW4sIHRoZSBudW1iZXIgb2Ygcm9zZXMgdGhhdCBzaG91bGQgYmUgaW4gZWFjaCBvZiB0aGUgcmVjdGFuZ3VsYXIgYXJlYXMsIGFuZCB0aGUgcG9zaXRpb25zIG9mIHRoZSByb3Nlcyw8XC9saT5cclxuXHQ8bGk+ZmluZHMgdGhlIGNvcm5lcnMgb2YgdHdvIHN1Y2ggcmVjdGFuZ3VsYXIgYXJlYXMgd2l0aCBtaW5pbXVtIHN1bSBvZiBwZXJpbWV0ZXJzIHRoYXQgc2F0aXNmeSB0aGUgZ2l2ZW4gY29uZGl0aW9ucyw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQgdGhlIG1pbmltdW0gc3VtIG9mIHBlcmltZXRlcnMgb2YgdHdvIG5vbi1vdmVybGFwcGluZyByZWN0YW5ndWxhciBhcmVhcywgZWFjaCBjb250YWluaW5nIGV4YWN0bHkgdGhlIGdpdmVuIG51bWJlciBvZiByb3NlcyAob3IgYSBzaW5nbGUgd29yZCBOTywgaWYgbm8gc3VjaCBwYWlyIG9mIGFyZWFzIGV4aXN0cykuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VyczogbCBhbmQgdyAoMSAmbGU7IGwsdyAmbGU7IDI1MCkgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlICZtZGFzaDsgdGhlIGxlbmd0aCBhbmQgdGhlIHdpZHRoIG9mIHRoZSBnYXJkZW4uIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnM6IG4gYW5kIGsgKDIgJmxlOyBuICZsZTsgNTAwMCAsIDEgJmxlOyBrICZsZTsgblwvMikgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlICZtZGFzaDsgdGhlIG51bWJlciBvZiByb3NlcyBpbiB0aGUgZ2FyZGVuIGFuZCB0aGUgbnVtYmVyIG9mIHJvc2VzIHRoYXQgc2hvdWxkIGJlIGluIGVhY2ggb2YgdGhlIHJlY3Rhbmd1bGFyIGFyZWFzLiBUaGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbiB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHJvc2VzLCBvbmUgcm9zZSBwZXIgbGluZS4gVGhlIChpKzIpLW5kIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIGw8c3ViPmk8XC9zdWI+LCB3PHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgbCwgMSAmbGU7IHc8c3ViPmk8XC9zdWI+ICZsZTsgdykgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlICZtZGFzaDsgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBzcXVhcmUgY29udGFpbmluZyB0aGUgaS10aCByb3NlLiBUd28gb3IgbW9yZSByb3NlcyBjYW4gb2NjdXIgaW4gdGhlIHNhbWUgc3F1YXJlLjxcL3A+XHJcblxyXG48cD5JbiA1MCUgb2YgdGVzdCBjYXNlcywgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIGdhcmRlbiB3aWxsIHNhdGlzZnkgbCx3ICZsZTsgNDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiBvbmx5IG9uZSBsaW5lIHdpdGggZXhhY3RseSBvbmUgaW50ZWdlciAmbWRhc2g7IHRoZSBtaW5pbXVtIHN1bSBvZiBwZXJpbWV0ZXJzIG9mIHR3byBub24tb3ZlcmxhcHBpbmcgcmVjdGFuZ3VsYXIgYXJlYXMsIGVhY2ggY29udGFpbmluZyBleGFjdGx5IGsgcm9zZXMsIG9yIGEgc2luZ2xlIHdvcmQgTk8sIGlmIG5vIHN1Y2ggcGFpciBvZiBhcmVhcyBleGlzdHMuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzU0ODRcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTkzcHg7IHdpZHRoOjIwOXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2005 1번

  • 문제를 번역한 사람: koosaga