시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWM2ZDBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1ZDNlZFx1Yzc3OCBsLHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGwsdyAmbGU7IDI1MCk8XC9wPlxyXG5cclxuPHA+XHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MDRcdWNjYjQgXHVjN2E1XHViYmY4XHVjNzU4IFx1YzIxOCBuLCBcdWI0NTAgXHVjMmI5XHVjNmQwXHVjNzc0XHVhYzAwIFx1ZDU2MFx1YjJmOVx1YmMxYlx1Yzc0NCBcdWM3YTVcdWJiZjhcdWM3NTggXHVjMjE4IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG4gJmxlOyA1MDAwICwgMSAmbGU7IGsgJmxlOyBuXC8yKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgaVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgaVx1YmM4OFx1YzlmOCBcdWM3YTVcdWJiZjhcdWFjMDAgXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBsPHN1Yj5pPFwvc3ViPiwgdzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBsPHN1Yj5pPFwvc3ViPiAmbGU7IGwsIDEgJmxlOyB3PHN1Yj5pPFwvc3ViPiAmbGU7IHcpIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViNDU4XHViODA4XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWMxOGNcdWM3NzggXHViNDUwIFx1YzYwMVx1YzVlZFx1Yzc0NCBcdWFkNmNcdWQ1NWMgXHViNGE0LCBcdWI0NTAgXHVjNjAxXHVjNWVkXHVjNzU4IFx1YjQ1OFx1YjgwOCBcdWFlMzhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM2MDFcdWM1ZWRcdWM3NDQgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM1YzhcdWIyZTRcdWJhNzQgTk9cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC81NDg0XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5M3B4OyB3aWR0aDoyMDlweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQ4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhcmRlbiIsImRlc2NyaXB0aW9uIjoiPHA+Qnl0ZW1hbiBvd25zIHRoZSBtb3N0IGJlYXV0aWZ1bCBnYXJkZW4gaW4gQnl0ZXRvd24uIEhlIHBsYW50ZWQgbiByb3NlcyBpbiBoaXMgZ2FyZGVuLiBTdW1tZXIgaGFzIGNvbWUgYW5kIHRoZSBmbG93ZXJzIGhhdmUgZ3Jvd24gYmlnIGFuZCBiZWF1dGlmdWwuIEJ5dGVtYW4gaGFzIHJlYWxpemVkIHRoYXQgaGUgaXMgbm90IGFibGUgdG8gdGFrZSBjYXJlIG9mIGFsbCB0aGUgcm9zZXMgb24gaGlzIG93bi4gSGUgaGFzIGRlY2lkZWQgdG8gZW1wbG95IHR3byBnYXJkZW5lcnMgdG8gaGVscCBoaW0uIEhlIHdhbnRzIHRvIHNlbGVjdCB0d28gcmVjdGFuZ3VsYXIgYXJlYXMsIHNvIHRoYXQgZWFjaCBvZiB0aGUgZ2FyZGVuZXJzIHdpbGwgdGFrZSBjYXJlIG9mIHRoZSByb3NlcyBpbnNpZGUgb25lIGFyZWEuIFRoZSBhcmVhcyBzaG91bGQgYmUgZGlzam9pbnQgYW5kIGVhY2ggc2hvdWxkIGNvbnRhaW4gZXhhY3RseSBrIHJvc2VzLjxcL3A+XHJcblxyXG48cD5CeXRlbWFuIHdhbnRzIHRvIG1ha2UgYSBmZW5jZSBzdXJyb3VuZGluZyB0aGUgcmVjdGFuZ3VsYXIgYXJlYXMsIGJ1dCBoZSBpcyBzaG9ydCBvZiBtb25leSwgc28gaGUgd2FudHMgdG8gdXNlIGFzIGxpdHRsZSBmZW5jZSBhcyBwb3NzaWJsZS4gWW91ciB0YXNrIGlzIHRvIGhlbHAgQnl0ZW1hbiBzZWxlY3QgdGhlIHR3byByZWN0YW5ndWxhciBhcmVhcy48XC9wPlxyXG5cclxuPHA+VGhlIGdhcmRlbiBmb3JtcyBhIHJlY3RhbmdsZSBsIG1ldGVycyBsb25nIGFuZCB3IG1ldGVycyB3aWRlLiBJdCBpcyBkaXZpZGVkIGludG8gbCZtaWRkb3Q7dyBzcXVhcmVzIG9mIHNpemUgMSBtZXRlciAmdGltZXM7IDEgbWV0ZXIgZWFjaC4gV2UgZml4IGEgY29vcmRpbmF0ZSBzeXN0ZW0gd2l0aCBheGVzIHBhcmFsbGVsIHRvIHRoZSBzaWRlcyBvZiB0aGUgZ2FyZGVuLiBBbGwgc3F1YXJlcyBoYXZlIGludGVnZXIgY29vcmRpbmF0ZXMgKHgseSkgc2F0aXNmeWluZyAxICZsZTsgeCAmbGU7IGwsIDEgJmxlOyB5ICZsZTsgdy4gRWFjaCBzcXVhcmUgbWF5IGNvbnRhaW4gYW55IG51bWJlciBvZiByb3Nlcy48XC9wPlxyXG5cclxuPHA+VGhlIHJlY3Rhbmd1bGFyIGFyZWFzLCB3aGljaCBtdXN0IGJlIHNlbGVjdGVkLCBzaG91bGQgaGF2ZSB0aGVpciBzaWRlcyBwYXJhbGxlbCB0byB0aGUgc2lkZXMgb2YgdGhlIGdhcmRlbiBhbmQgdGhlIHNxdWFyZXMgaW4gdGhlaXIgY29ybmVycyBzaG91bGQgaGF2ZSBpbnRlZ2VyIGNvb3JkaW5hdGVzLiBGb3IgMSAmbGU7IGw8c3ViPjE8XC9zdWI+ICZsZTsgbDxzdWI+MjxcL3N1Yj4gJmxlOyBsIGFuZCAxICZsZTsgdzxzdWI+MTxcL3N1Yj4gJmxlOyB3PHN1Yj4yPFwvc3ViPiAmbGU7IHcsIGEgcmVjdGFuZ3VsYXIgYXJlYSB3aXRoIGNvcm5lcnMgKGw8c3ViPjE8XC9zdWI+LHc8c3ViPjE8XC9zdWI+KSwgKGw8c3ViPjE8XC9zdWI+LHc8c3ViPjI8XC9zdWI+KSwgKGw8c3ViPjI8XC9zdWI+LHc8c3ViPjE8XC9zdWI+KSBhbmQgKGw8c3ViPjI8XC9zdWI+LHc8c3ViPjI8XC9zdWI+KTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5jb250YWlucyBhbGwgdGhlIHNxdWFyZXMgd2l0aCBjb29yZGluYXRlcyAoeCx5KSBzYXRpc2Z5aW5nIGw8c3ViPjE8XC9zdWI+ICZsZTsgeCAmbGU7IGw8c3ViPjI8XC9zdWI+IGFuZCB3PHN1Yj4xPFwvc3ViPiAmbGU7IHkgJmxlOyB3PHN1Yj4yPFwvc3ViPiwgYW5kPFwvbGk+XHJcblx0PGxpPmhhcyBwZXJpbWV0ZXIgMiAmbWlkZG90OyAobDxzdWI+MjxcL3N1Yj4gJm1pbnVzOyBsPHN1Yj4xPFwvc3ViPiArIDEpICsgMiAmbWlkZG90OyAodzxzdWI+MjxcL3N1Yj4gJm1pbnVzOyB3PHN1Yj4xPFwvc3ViPiArIDEpLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSB0d28gcmVjdGFuZ3VsYXIgYXJlYXMgbXVzdCBiZSBkaXNqb2ludCwgdGhhdCBpcyB0aGV5IGNhbm5vdCBjb250YWluIGEgY29tbW9uIHNxdWFyZS4gRXZlbiBpZiB0aGV5IGhhdmUgYSBjb21tb24gc2lkZSwgb3IgcGFydCBvZiBpdCwgdGhleSBtdXN0IGJlIHN1cnJvdW5kZWQgYnkgc2VwYXJhdGUgZmVuY2VzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0sIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIGdhcmRlbiwgdGhlIG51bWJlciBvZiByb3NlcyBpbiB0aGUgZ2FyZGVuLCB0aGUgbnVtYmVyIG9mIHJvc2VzIHRoYXQgc2hvdWxkIGJlIGluIGVhY2ggb2YgdGhlIHJlY3Rhbmd1bGFyIGFyZWFzLCBhbmQgdGhlIHBvc2l0aW9ucyBvZiB0aGUgcm9zZXMsPFwvbGk+XHJcblx0PGxpPmZpbmRzIHRoZSBjb3JuZXJzIG9mIHR3byBzdWNoIHJlY3Rhbmd1bGFyIGFyZWFzIHdpdGggbWluaW11bSBzdW0gb2YgcGVyaW1ldGVycyB0aGF0IHNhdGlzZnkgdGhlIGdpdmVuIGNvbmRpdGlvbnMsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0byB0aGUgc3RhbmRhcmQgb3V0cHV0IHRoZSBtaW5pbXVtIHN1bSBvZiBwZXJpbWV0ZXJzIG9mIHR3byBub24tb3ZlcmxhcHBpbmcgcmVjdGFuZ3VsYXIgYXJlYXMsIGVhY2ggY29udGFpbmluZyBleGFjdGx5IHRoZSBnaXZlbiBudW1iZXIgb2Ygcm9zZXMgKG9yIGEgc2luZ2xlIHdvcmQgTk8sIGlmIG5vIHN1Y2ggcGFpciBvZiBhcmVhcyBleGlzdHMpLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBzdGFuZGFyZCBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnM6IGwgYW5kIHcgKDEgJmxlOyBsLHcgJmxlOyAyNTApIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSAmbWRhc2g7IHRoZSBsZW5ndGggYW5kIHRoZSB3aWR0aCBvZiB0aGUgZ2FyZGVuLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzOiBuIGFuZCBrICgyICZsZTsgbiAmbGU7IDUwMDAgLCAxICZsZTsgayAmbGU7IG5cLzIpIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSAmbWRhc2g7IHRoZSBudW1iZXIgb2Ygcm9zZXMgaW4gdGhlIGdhcmRlbiBhbmQgdGhlIG51bWJlciBvZiByb3NlcyB0aGF0IHNob3VsZCBiZSBpbiBlYWNoIG9mIHRoZSByZWN0YW5ndWxhciBhcmVhcy4gVGhlIGZvbGxvd2luZyBuIGxpbmVzIGNvbnRhaW4gdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSByb3Nlcywgb25lIHJvc2UgcGVyIGxpbmUuIFRoZSAoaSsyKS1uZCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBsPHN1Yj5pPFwvc3ViPiwgdzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBsPHN1Yj5pPFwvc3ViPiAmbGU7IGwsIDEgJmxlOyB3PHN1Yj5pPFwvc3ViPiAmbGU7IHcpIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSAmbWRhc2g7IHRoZSBjb29yZGluYXRlcyBvZiB0aGUgc3F1YXJlIGNvbnRhaW5pbmcgdGhlIGktdGggcm9zZS4gVHdvIG9yIG1vcmUgcm9zZXMgY2FuIG9jY3VyIGluIHRoZSBzYW1lIHNxdWFyZS48XC9wPlxyXG5cclxuPHA+SW4gNTAlIG9mIHRlc3QgY2FzZXMsIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBnYXJkZW4gd2lsbCBzYXRpc2Z5IGwsdyAmbGU7IDQwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25seSBvbmUgbGluZSB3aXRoIGV4YWN0bHkgb25lIGludGVnZXIgJm1kYXNoOyB0aGUgbWluaW11bSBzdW0gb2YgcGVyaW1ldGVycyBvZiB0d28gbm9uLW92ZXJsYXBwaW5nIHJlY3Rhbmd1bGFyIGFyZWFzLCBlYWNoIGNvbnRhaW5pbmcgZXhhY3RseSBrIHJvc2VzLCBvciBhIHNpbmdsZSB3b3JkIE5PLCBpZiBubyBzdWNoIHBhaXIgb2YgYXJlYXMgZXhpc3RzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC81NDg0XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5M3B4OyB3aWR0aDoyMDlweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 2005 1번

  • 문제를 번역한 사람: koosaga