시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB268633.333%

문제

창영제국의 황제 김상근이 세상을 떠났다. 사람들은 그가 가졌던 제국이 어떻게 자식들에게 나누어질 것인지 궁금해하기 시작했다. 제국은 직사각형 모양이고, N개의 도시가 있다.

땅은 K-1개의 선분으로 나누어야 한다. 선분은 지도의 축과 평행이어야 한다.

나누어진 지도에는 정확하게 K개의 직사각형이 있어야 하고, 모두 같은 높이(땅을 수직으로 나누었을 때)나 같은 너비(수평으로 나누었을 때)를 가지고 있어야 한다. 선분은 도시를 지나면 안 된다.

모든 상근이의 자식들은 K개의 나누어진 제국 하나를 임의로 받게 되고, 그 땅에 포함된 도시를 가질 수 있다.

모든 자식들에게 공평하게 땅을 나누어주기 위해서 각 자식들에게 N/K의 도시를 주려고 한다. 이 N/K를 기준값이라고 한다. 하지만, 기준값은 정수가 아닐수도 있기 때문에, 각각의 자식들은 최대한 기준값에 가깝게 도시를 얻기를 원한다.

각 자식의 불공평점수는 그 자식이 가진 도시의 수와 기준값과의 차이이다. 모든 자식의 불공평점수의 평균을 최소로 하려고 한다.

위의 예는 땅에 도시가 6개, 상근이의 자식이 3명 있을 때이다. (기준값 = 6/3 = 2.0) 왼쪽 그림은 제국의 지도이다. 가운데 그림처럼 나누었을 때, 가운데 영역에는 도시가 3개 있다. 이 땅을 받는 자식의 불공평점수는 |3-2| = 1이다. 왼쪽 영역은 2개의 도시가 있기 때문에 불공평점수는 0이고, 오른쪽 영역은 1개의 도시가 있기 때문에 불공평점수는 1이다. 따라서, 불공평점수의 평균은 2/3이 된다.

가장 오른쪽 그림은 모두 같은 수의 도시를 받게 되므로 불공평점수의 평균이 0이 된다.

땅과 도시의 위치가 주어졌을 때, 공평하게 땅을 나누어 불공평점수의 평균을 최소로 하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 N+1줄로 이루어져 있다.

테스트 케이스의 첫째 줄에는 도시의 수 N(N ≤ 100,000)과 자식의 수 K(K ≤ 10)가 주어진다. 항상 K ≤ N이다.

다음 N개의 줄에는 도시의 좌표 (x,y)가 주어진다. (0 ≤ x,y ≤ 100,000) x와 y는 정수이다. 원래 지도에 있는 도시의 좌표를 가까운 정수로 반올림해서 나타낸 것이기 때문에, 같은 위치에 하나보다 많은 도시가 있을 수도 있다. 모든 좌표를 포함하는 가상의 직사각형이 지도의 경계라고 생각하면 된다. 

나누는 선은 정수 좌표를 갖지 않아도 된다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 불공평점수의 평균값의 최솟값을 출력한다. 불공평점수의 평균값은 A/B와 같은 형식으로 출력하고, 기약분수이어야 한다. 만약 평균이 정수일 경우에는 B=1로 출력해야 한다.

예제 입력 1

6 3
0 4
1 3
2 3
3 1
4 4
5 0
4 3
0 0
0 1
1 1
1 0
0 0

예제 출력 1

1. 0/1
2. 8/9
W3sicHJvYmxlbV9pZCI6IjQ4OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI1NDUgXHViMDk4XHViMjA0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM4MWNcdWFkNmRcdWM3NTggXHVkNjY5XHVjODFjIFx1YWU0MFx1YzBjMVx1YWRmY1x1Yzc3NCBcdWMxMzhcdWMwYzFcdWM3NDQgXHViNWEwXHViMGFjXHViMmU0LiBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHVhZGY4XHVhYzAwIFx1YWMwMFx1Yzg0Y1x1YjM1OCBcdWM4MWNcdWFkNmRcdWM3NzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1Yzc5MFx1YzJkZFx1YjRlNFx1YzVkMFx1YWM4YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzggXHVhYzgzXHVjNzc4XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuIFx1YzgxY1x1YWQ2ZFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc0XHVhY2UwLCBOXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjU0NVx1Yzc0MCBLLTFcdWFjMWNcdWM3NTggXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWM5YzBcdWIzYzRcdWM3NTggXHVjZDk1XHVhY2ZjIFx1ZDNjOVx1ZDU4OVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjA5OFx1YjIwNFx1YzViNFx1YzljNCBcdWM5YzBcdWIzYzRcdWM1ZDBcdWIyOTQgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIEtcdWFjMWNcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM3NDAgXHViMTkyXHVjNzc0KFx1YjU0NVx1Yzc0NCBcdWMyMThcdWM5YzFcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHVjNzQ0IFx1YjU0YylcdWIwOTggXHVhYzE5XHVjNzQwIFx1YjEwOFx1YmU0NChcdWMyMThcdWQzYzlcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWM4XHVjNzQ0IFx1YjU0YylcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVjOWMwXHViMDk4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNzkwXHVjMmRkXHViNGU0XHVjNzQwIEtcdWFjMWNcdWM3NTggXHViMDk4XHViMjA0XHVjNWI0XHVjOWM0IFx1YzgxY1x1YWQ2ZCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNzg0XHVjNzU4XHViODVjIFx1YmMxYlx1YWM4YyBcdWI0MThcdWFjZTAsIFx1YWRmOCBcdWI1NDVcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWFjMDBcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzc5MFx1YzJkZFx1YjRlNFx1YzVkMFx1YWM4YyBcdWFjZjVcdWQzYzlcdWQ1NThcdWFjOGMgXHViNTQ1XHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNFx1YzhmY1x1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhYzAxIFx1Yzc5MFx1YzJkZFx1YjRlNFx1YzVkMFx1YWM4YyBOXC9LXHVjNzU4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgTlwvS1x1Yjk3YyBcdWFlMzBcdWM5MDBcdWFjMTJcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWUzMFx1YzkwMFx1YWMxMlx1Yzc0MCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmQwXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3OTBcdWMyZGRcdWI0ZTRcdWM3NDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YWUzMFx1YzkwMFx1YWMxMlx1YzVkMCBcdWFjMDBcdWFlNWRcdWFjOGMgXHViM2M0XHVjMmRjXHViOTdjIFx1YzViYlx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM3OTBcdWMyZGRcdWM3NTggXHViZDg4XHVhY2Y1XHVkM2M5XHVjODEwXHVjMjE4XHViMjk0IFx1YWRmOCBcdWM3OTBcdWMyZGRcdWM3NzQgXHVhYzAwXHVjOWM0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMThcdWM2NDAgXHVhZTMwXHVjOTAwXHVhYzEyXHVhY2ZjXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzc5MFx1YzJkZFx1Yzc1OCBcdWJkODhcdWFjZjVcdWQzYzlcdWM4MTBcdWMyMThcdWM3NTggXHVkM2M5XHVhZGUwXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xhbmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIzcHg7IHdpZHRoOjYyOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWIyOTQgXHViNTQ1XHVjNWQwIFx1YjNjNFx1YzJkY1x1YWMwMCA2XHVhYzFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjNzkwXHVjMmRkXHVjNzc0IDNcdWJhODUgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1Yzc3NFx1YjJlNC4gKFx1YWUzMFx1YzkwMFx1YWMxMiA9IDZcLzMgPSAyLjApIFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjODFjXHVhZDZkXHVjNzU4IFx1YzljMFx1YjNjNFx1Yzc3NFx1YjJlNC4gXHVhYzAwXHVjNmI0XHViMzcwIFx1YWRmOFx1YjliY1x1Y2M5OFx1YjdmYyBcdWIwOThcdWIyMDRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM2YjRcdWIzNzAgXHVjNjAxXHVjNWVkXHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1YWMwMCAzXHVhYzFjIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0NVx1Yzc0NCBcdWJjMWJcdWIyOTQgXHVjNzkwXHVjMmRkXHVjNzU4IFx1YmQ4OFx1YWNmNVx1ZDNjOVx1YzgxMFx1YzIxOFx1YjI5NCB8My0yfCA9IDFcdWM3NzRcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWM2MDFcdWM1ZWRcdWM3NDAgMlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJkODhcdWFjZjVcdWQzYzlcdWM4MTBcdWMyMThcdWIyOTQgMFx1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzYwMVx1YzVlZFx1Yzc0MCAxXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1YWMwMCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YmQ4OFx1YWNmNVx1ZDNjOVx1YzgxMFx1YzIxOFx1YjI5NCAxXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YmQ4OFx1YWNmNVx1ZDNjOVx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NDAgMlwvM1x1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWJjMWJcdWFjOGMgXHViNDE4XHViYmMwXHViODVjIFx1YmQ4OFx1YWNmNVx1ZDNjOVx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NzQgMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjU0NVx1YWNmYyBcdWIzYzRcdWMyZGNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWNmNVx1ZDNjOVx1ZDU1OFx1YWM4YyBcdWI1NDVcdWM3NDQgXHViMDk4XHViMjA0XHVjNWI0IFx1YmQ4OFx1YWNmNVx1ZDNjOVx1YzgxMFx1YzIxOFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBOKzFcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggTihOICZsZTsgMTAwLDAwMClcdWFjZmMgXHVjNzkwXHVjMmRkXHVjNzU4IFx1YzIxOCBLKEsgJmxlOyAxMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NmRcdWMwYzEgSyAmbGU7IE5cdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjODhjXHVkNDVjICh4LHkpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyB4LHkgJmxlOyAxMDAsMDAwKSB4XHVjNjQwIHlcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM2ZDBcdWI3OTggXHVjOWMwXHViM2M0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWM4MTVcdWMyMThcdWI4NWMgXHViYzE4XHVjNjJjXHViOWJjXHVkNTc0XHVjMTFjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFjMTlcdWM3NDAgXHVjNzA0XHVjZTU4XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHViM2M0XHVjMmRjXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWFjMDBcdWMwYzFcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWI3N2NcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMDk4XHViMjA0XHViMjk0IFx1YzEyMFx1Yzc0MCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHViOTdjIFx1YWMxNlx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWM2NDAgXHViZDg4XHVhY2Y1XHVkM2M5XHVjODEwXHVjMjE4XHVjNzU4IFx1ZDNjOVx1YWRlMFx1YWMxMlx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJkODhcdWFjZjVcdWQzYzlcdWM4MTBcdWMyMThcdWM3NTggXHVkM2M5XHVhZGUwXHVhYzEyXHVjNzQwIEFcL0JcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWQzYzlcdWFkZTBcdWM3NzQgXHVjODE1XHVjMjE4XHVjNzdjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBCPTFcdWI4NWMgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0ODk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFuZCBEaXZpc2lvbiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGtpbmcgb2YgdGhlIEZhciwgRmFyIEF3YXkgS2luZ2RvbSBoYXMgcGFzc2VkLWF3YXkgYW5kIHRoZSBraW5nZG9tIG11c3QgYmUgc3BsaXQgYW1vbmdzdCBoaXMgSyBzb25zLiBUaGUga2luZ2RvbSwgd2hpY2ggY2FuIGJlIGRyYXduIG9uIGEgcmVjdGFuZ3VsYXIgbWFwLCBjb25zaXN0cyBvZiBOIGNpdGllcy4gVG8gZGl2aWRlIHRoZSBsYW5kLCB0aGV5IHdpbGwgZHJhdyBLICZtaW51czsgMSBzdHJhaWdodCBzZWdtZW50cyBvbiB0aGUgbWFwLCBhbGwgb2YgdGhlbSBwYXJhbGxlbCB0byBlaXRoZXIgdGhlIHZlcnRpY2FsIG9yIHRoZSBob3Jpem9udGFsIGF4aXMgb2YgdGhlIG1hcC4gVGhpcyBkaXZpZGVzIHRoZSBtYXAgaW50byBleGFjdGx5IEsgcmVjdGFuZ2xlcywgYWxsIGhhdmluZyBlcXVhbCBoZWlnaHRzIChpZiB0aGUgZGl2aWRpbmcgbGluZXMgd2hlcmUgdmVydGljYWwpLCBvciBlcXVhbCB3aWR0aHMgKGlmIHRoZSBkaXZpZGluZyBsaW5lcyB3aGVyZSBob3Jpem9udGFsKS4gTm8gc2VnbWVudCBzaG91bGQgcGFzcyB0aHJvdWdoIGFueSBvZiB0aGUgY2l0aWVzLiBFYWNoIHNvbiB3aWxsIHRoZW4gYmUgYXNzaWduZWQgb25lIHJhbmRvbSByZWdpb24gb3V0IG9mIHRoZSBLIHJlZ2lvbnMgYW5kIHRoZSBjaXRpZXMgaW5zaWRlIHRoYXQgcmVnaW9uIHdpbGwgYmUgaGlzIHNoYXJlLjxcL3A+XHJcblxyXG48cD5PZiBjb3Vyc2UsIHRoZXkgd2FudCB0aGUgZGl2aXNpb24gdG8gYmUgYXMgZmFpciBhcyBwb3NzaWJsZTogdGhlb3JldGljYWxseSwgaW4gdGhlIGZhaXJlc3QgZGl2aXNpb24sIGVhY2ggc29uIHNob3VsZCBnZXQgTlwvSyBjaXRpZXMgKHdlJnJzcXVvO2xsIGNhbGwgdGhpcyB2YWx1ZSB0aGUgYmFzZWxpbmUpLCBidXQgc2luY2UgdGhlIGJhc2VsaW5lIGlzbiZyc3F1bzt0IGFsd2F5cyBhIHdob2xlIG51bWJlciwgZWFjaCBvZiB0aGUgc29ucyB3YW50cyB0byBiZSBhcyBjbG9zZSBhcyBwb3NzaWJsZSB0byB0aGUgYmFzZWxpbmUuIFdlIHdpbGwgY2FsY3VsYXRlIHRoZSB1bmZhaXJuZXNzIG9mIGVhY2ggc29uIGFzIHRoZSBhYnNvbHV0ZSBkaVx1ZmIwMGVyZW5jZSBiZXR3ZWVuIHRoZSBudW1iZXIgb2YgY2l0aWVzIGFzc2lnbmVkIHRvIGhpbSBhbmQgdGhlIGJhc2VsaW5lLiBUaGUgZmFpcmVzdCBkaXZpc2lvbiBpcyB0aGUgb25lIHRoYXQgbWluaW1pemVzIHRoZSBhdmVyYWdlIHVuZmFpcm5lc3Mgb2YgYWxsIHRoZSBzb25zLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xhbmQoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTY2cHg7IHdpZHRoOjY0MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkNvbnNpZGVyIHRoZSBleGFtcGxlIGFib3ZlIHdpdGggMyBzb25zIGFuZCA2IGNpdGllcyAoc28gdGhlIGJhc2VsaW5lIGlzIDZcLzMgPSAyLjApIEZpZ3VyZSAoYSkgaXMgdGhlIG9yaWdpbmFsIG1hcC4gRmlndXJlIChiKSBzaG93cyBhIG5vbi1vcHRpbWFsIGRpdmlzaW9uICh0aGUgZGFzaGVkIGxpbmVzIGFyZSB0aGUgMiBkaXZpZGluZyBsaW5lcy4pIEluIHRoaXMgY2FzZSwgdGhlIG1pZGRsZSByZWdpb24gY29udGFpbnMgMyBjaXRpZXMgKHVuZmFpcm5lc3Mgb2YgfDMgJm1pbnVzOyAyfCA9IDEpLCB0aGUgbGVmdCByZWdpb24gY29udGFpbnMgMSBjaXR5ICh1bmZhaXJuZXNzIG9mIHwxICZtaW51czsgMnwgPSAxKSwgd2hpbGUgdGhlIHJpZ2h0IHJlZ2lvbiBjb250YWlucyAyIGNpdGllcyAocGVyZmVjdGx5IGZhaXIsIHVuZmFpcm5lc3Mgb2YgMCksIHNvIHRoZSBhdmVyYWdlIHVuZmFpcm5lc3MgaXMgMlwvMy48XC9wPlxyXG5cclxuPHA+RmlndXJlIChjKSBvbiB0aGUgcmlnaHQgc2hvd3MgdGhlIG9wdGltYWwgZGl2aXNpb24gc2luY2UgYWxsIHRocmVlIHJlZ2lvbnMgY29udGFpbiB0aGUgc2FtZSBudW1iZXIgb2YgY2l0aWVzIGZvciBhbiBhdmVyYWdlIHVuZmFpcm5lc3Mgb2YgMC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSB0aGUgZmFpcmVzdCBsYW5kIGRpdmlzaW9uIGZvciBhIGdpdmVuIGtpbmdkb20uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gb25lIG9yIG1vcmUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgZGVzY3JpYmVkIG9uIE4gKyAxIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2Ugc3BlY2lcdWZiMDFlcyB0d28gcG9zaXRpdmUgaW50ZWdlcnM6IChOICZsZTsgMTAwLCAwMDApIGFuZCAoSyAmbGU7IDEwKSB3aGVyZSBOIGlzIHRoZSBudW1iZXIgb2YgY2l0aWVzIGFuZCBLIGlzIG51bWJlciBvZiBjaGlsZHJlbi4gTm90ZSB0aGF0IEsgJmxlOyBOLjxcL3A+XHJcblxyXG48cD5OIGxpbmVzIGZvbGxvd3MsIGVhY2ggZGVzY3JpYmluZyB0aGUgY29vcmRpbmF0ZXMgb2YgYSBjaXR5IGJ5IHNwZWNpZnlpbmcgdHdvIGludGVnZXJzICh4LCB5KSB3aGVyZSAwICZsZTsgeCwgeSAmbGU7IDEwMCwgMDAwLiBTaW5jZSBjb29yZGluYXRlcyBhcmUgcm91bmRlZCB0byB0aGUgbmVhcmVzdCBpbnRlZ2VyLCBtb3JlIHRoYW4gb25lIGNpdHkgY291bGQgaGF2ZSB0aGUgZXhhY3Qgc2FtZSBjb29yZGluYXRlIG9uIHRoZSBtYXAuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIG1hcCBvZiB0aGUga2luZ2RvbSBpcyBhbnkgcmVjdGFuZ2xlIHRoYXQgY29udGFpbnMgYWxsIG9mIHRoZSBnaXZlbiBwb2ludHMgKGFsdGhvdWdoIHN1Y2ggaW5mb3JtYXRpb24gaXMgbm90IG5lZWRlZCBieSB0aGUgcHJvZ3JhbS4pIE5vdGUgYWxzbyB0aGF0IHdoaWxlIGFsbCBjaXRpZXMgbGllIG9uIGludGVnZXIgY29vcmRpbmF0ZXMsIHRoZSBkaXZpZGluZyBsaW5lcyBuZWVkIG5vdCBiZS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgbGluZSBvZiB0aGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgdHdvIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGZvbGxvd2luZyBsaW5lOjxcL3A+XHJcblxyXG48cHJlPmsuIEFcL0I8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBrIGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBhdCBvbmUsKSBhbmQgQVwvQiBpcyB0aGUgbWluaW11bSBhdmVyYWdlIHRoYXQgY291bGQgYmUgb2J0YWluZWQuIEFcL0Igc2hvdWxkIGJlIGFuIGlycmVkdWNpYmxlIGZyYWN0aW9uLiBMZXQgQj0xIHdoZW4gdGhlIHJlc3VsdCBpcyBhIHdob2xlIG51bWJlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2009 Arab Collegiate Programming Contest H번

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