시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 1155 279 174 20.739%

문제

매우 드물고 비싼 금속을 지하에서 찾아냈다. 금속은 땅 속에 넓게 흩어져 있기 때문에 신중하게 채굴 계획을 세우려고 한다. 따라서, 그림 1과 같이 수직 엘리베이터(vertical elevator)로 연결된 여러 개의 수평 터널(horizontal tunnel)을 만들기로 했다. 모든 엘리베이터는 한 터널의 오른쪽 끝과 다른 터널의 왼쪽 끝을 연결한다. 또, 터널과 엘리베이터의 연결 구조는 땅에 대해서 단조로워야 한다. 즉, 가장 왼쪽에 있는 터널의 끝에서 시작해서 가장 오른족에 있는 터널의 끝에 이동할 때, 다시 왼쪽으로 이동하는 일 없이 모든 터널을 지날 수 있어야 한다.

예산이 제한되어 있기 때문에, 수평 터널을 k개만 만들기로 했다. (k는 양의 정수) 따라서, 수평 터널을 연결할 수직 엘리베이터는 최대 k-1개 만들 수 있다. 이제, 수평 터널과 각각의 금속을 연결하는 수직 터널을 만들어야 한다. 한 금속을 채굴하는데 드는 비용은 수평 터널과의 수직 거리이다. 금속 n개를 채굴하는데 필요한 비용은 각 금속의 채굴 비용 중 최댓값이다.

그림 1. 금속이 15개, k=3인 경우의 채굴 계획. 이 계획에서 최대 거리는 오른쪽 빨간색으로 표시된 거리이고, 그 거리가 이 계획의 채굴 비용이다.

그림 1과 같이, 각 금속은 2차원 평면 위의 점으로 나타낼 수 있고, 수평 터널은 수평선, 수직 터널과 엘리베이터는 수직선으로 나타낼 수 있다. 점 n개 P = {p1, p2, ..., pn}와 양의 정수 k가 주어진다. 이때, 금속 pi를 채굴하는데 필요한 비용 cost(pi)은 수평 터널과 떨어진 수직 거리이다. P = {p1, p2, ... pn}의 채굴 비용 cost(P)는 모든 cost(Pi)중 최댓값 (max1≤i≤ncost(pi)) 이다. 이때, cost(P)를 최소로 만드는 (최대) k개 수평 터널의 위치를 결정해야 한다.

점 n개의 집합 P와 양의 정수 k가 주어졌을 때, cost(P)의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 점(금속)의 개수 n과 k가 주어진다. (2 ≤ n ≤ 10,000) 다음 줄에는 점 p1, p2, ..., pn의 좌표를 나타내는 정수 2n개 (x1, y1), (x2, y2), ..., (xn, yn)이 주어진다. (-100,000,000 ≤ xi, yi ≤ 100,000,000) 모든 좌표는 공백으로 구분되어 있고, 두 점이 같은 x좌표를 갖는 경우는 없다.

출력

각 테스트 케이스마다 cost(P)의 최솟값을 출력한다. 항상 소수점 둘째 자리에서 반올림해서 첫째 자리까지 출력한다.

예제 입력 1

2
3 1
-1 0 0 0 1 0
5 2
2 5 9 2 6 3 -2 2 7 0

예제 출력 1

0.0
1.5
W3sicHJvYmxlbV9pZCI6Ijk0NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhNTRcdWQwYzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjllNFx1YzZiMCBcdWI0ZGNcdWJiM2NcdWFjZTAgXHViZTQ0XHVjMmZjIFx1YWUwOFx1YzE4ZFx1Yzc0NCBcdWM5YzBcdWQ1NThcdWM1ZDBcdWMxMWMgXHVjYzNlXHVjNTQ0XHViMGM4XHViMmU0LiBcdWFlMDhcdWMxOGRcdWM3NDAgXHViNTQ1IFx1YzE4ZFx1YzVkMCBcdWIxMTNcdWFjOGMgXHVkNzY5XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMmUwXHVjOTExXHVkNTU4XHVhYzhjIFx1Y2M0NFx1YWQ3NCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHVjMTM4XHVjNmIwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjhcdWI5YmMgMVx1YWNmYyBcdWFjMTlcdWM3NzQgXHVjMjE4XHVjOWMxIFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMCh2ZXJ0aWNhbCBlbGV2YXRvcilcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVjMjE4XHVkM2M5IFx1ZDEzMFx1YjExMChob3Jpem9udGFsIHR1bm5lbClcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzVkOFx1YjlhY1x1YmNhMFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWQ1NWMgXHVkMTMwXHViMTEwXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWIwNWRcdWFjZmMgXHViMmU0XHViOTc4IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM2N2NcdWNhYmQgXHViMDVkXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWQxMzBcdWIxMTBcdWFjZmMgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHVjNzU4IFx1YzVmMFx1YWNiMCBcdWFkNmNcdWM4NzBcdWIyOTQgXHViNTQ1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWIyZThcdWM4NzBcdWI4NWNcdWM2Y2NcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWIwNWRcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWM4NzFcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWIwNWRcdWM1ZDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YywgXHViMmU0XHVjMmRjIFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVjNzdjIFx1YzVjNlx1Yzc3NCBcdWJhYThcdWI0ZTAgXHVkMTMwXHViMTEwXHVjNzQ0IFx1YzljMFx1YjBhMCBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjMGIwXHVjNzc0IFx1YzgxY1x1ZDU1Y1x1YjQxOFx1YzViNCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyMThcdWQzYzkgXHVkMTMwXHViMTEwXHVjNzQ0IGtcdWFjMWNcdWI5Y2MgXHViOWNjXHViNGU0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gKGtcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCkgXHViNTMwXHViNzdjXHVjMTFjLCBcdWMyMThcdWQzYzkgXHVkMTMwXHViMTEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMThcdWM5YzEgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViMjk0IFx1Y2Q1Y1x1YjMwMCBrLTFcdWFjMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzgxYywgXHVjMjE4XHVkM2M5IFx1ZDEzMFx1YjExMFx1YWNmYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZTA4XHVjMThkXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM5YzEgXHVkMTMwXHViMTEwXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWFlMDhcdWMxOGRcdWM3NDQgXHVjYzQ0XHVhZDc0XHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgXHVjMjE4XHVkM2M5IFx1ZDEzMFx1YjExMFx1YWNmY1x1Yzc1OCBcdWMyMThcdWM5YzEgXHVhYzcwXHViOWFjXHVjNzc0XHViMmU0LiBcdWFlMDhcdWMxOGQgblx1YWMxY1x1Yjk3YyBcdWNjNDRcdWFkNzRcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWFjMDEgXHVhZTA4XHVjMThkXHVjNzU4IFx1Y2M0NFx1YWQ3NCBcdWJlNDRcdWM2YTkgXHVjOTExIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWV0YWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzYxcHg7IHdpZHRoOjY3MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAxLiBcdWFlMDhcdWMxOGRcdWM3NzQgMTVcdWFjMWMsIGs9M1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjYzQ0XHVhZDc0IFx1YWNjNFx1ZDY4ZC4gXHVjNzc0IFx1YWNjNFx1ZDY4ZFx1YzVkMFx1YzExYyBcdWNkNWNcdWIzMDAgXHVhYzcwXHViOWFjXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJlNjhcdWFjMDRcdWMwYzlcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDFjIFx1YWM3MFx1YjlhY1x1Yzc3NFx1YWNlMCwgXHVhZGY4IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWM3NzQgXHVhY2M0XHVkNjhkXHVjNzU4IFx1Y2M0NFx1YWQ3NCBcdWJlNDRcdWM2YTlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAxXHVhY2ZjIFx1YWMxOVx1Yzc3NCwgXHVhYzAxIFx1YWUwOFx1YzE4ZFx1Yzc0MCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM3NTggXHVjODEwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWMyMThcdWQzYzkgXHVkMTMwXHViMTEwXHVjNzQwIFx1YzIxOFx1ZDNjOVx1YzEyMCwgXHVjMjE4XHVjOWMxIFx1ZDEzMFx1YjExMFx1YWNmYyBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWIyOTQgXHVjMjE4XHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM4MTAgblx1YWMxYyBQID0ge3A8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgLi4uLCBwPHN1Yj5uPFwvc3ViPn1cdWM2NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFlMDhcdWMxOGQgcDxzdWI+aTxcL3N1Yj5cdWI5N2MgXHVjYzQ0XHVhZDc0XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJlNDRcdWM2YTkgY29zdChwPHN1Yj5pPFwvc3ViPilcdWM3NDAgXHVjMjE4XHVkM2M5IFx1ZDEzMFx1YjExMFx1YWNmYyBcdWI1YThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjOWMxIFx1YWM3MFx1YjlhY1x1Yzc3NFx1YjJlNC4gUCA9IHtwPHN1Yj4xPFwvc3ViPiwgcDxzdWI+MjxcL3N1Yj4sIC4uLiBwPHN1Yj5uPFwvc3ViPn1cdWM3NTggXHVjYzQ0XHVhZDc0IFx1YmU0NFx1YzZhOSBjb3N0KFApXHViMjk0IFx1YmFhOFx1YjRlMCBjb3N0KFA8c3ViPmk8XC9zdWI+KVx1YzkxMSBcdWNkNWNcdWIzMTNcdWFjMTIgKG1heDxzdWI+MSZsZTtpJmxlO248XC9zdWI+Y29zdChwPHN1Yj5pPFwvc3ViPikpIFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBjb3N0KFApXHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgKFx1Y2Q1Y1x1YjMwMCkga1x1YWMxYyBcdWMyMThcdWQzYzkgXHVkMTMwXHViMTEwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWFjYjBcdWM4MTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTAgblx1YWMxY1x1Yzc1OCBcdWM5ZDFcdWQ1NjkgUFx1YzY0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgY29zdChQKVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMChcdWFlMDhcdWMxOGQpXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVhY2ZjIGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG4gJmxlOyAxMCwwMDApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwIHA8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgLi4uLCBwPHN1Yj5uPFwvc3ViPlx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCAyblx1YWMxYyAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSwgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPiksIC4uLiwgKHg8c3ViPm48XC9zdWI+LCB5PHN1Yj5uPFwvc3ViPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwMCwwMDAsMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLDAwMCwwMDApIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YjQ1MCBcdWM4MTBcdWM3NzQgXHVhYzE5XHVjNzQwIHhcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzE2XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgY29zdChQKVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NmRcdWMwYzEgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWM1ZDBcdWMxMWMgXHViYzE4XHVjNjJjXHViOWJjXHVkNTc0XHVjMTFjIFx1Y2NhYlx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0NjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNZXRhbCIsImRlc2NyaXB0aW9uIjoiPHA+V2UgZm91bmQgcmFyZSBhbmQgdmFsdWFibGUgbWV0YWxzIHVuZGVyIHRoZSBncm91bmQuIFRoZSBtZXRhbHMgYXJlIHdpZGVseSBzY2F0dGVyZWQgdW5kZXJncm91bmQsIHNvIHdlIG5lZWQgYSBjYXJlZnVsIHBsYW4gdG8gZGlnIHRoZW0uIEZvciB0aGlzLCB3ZSBhcmUgZ29pbmcgdG8gYnVpbGQgYSBudW1iZXIgb2YgaG9yaXpvbnRhbCB0dW5uZWxzIGNvbm5lY3RlZCBieSB2ZXJ0aWNhbCBlbGV2YXRvcnMsIGFzIGluIEZpZ3VyZSAxLiBFdmVyeSB2ZXJ0aWNhbCBlbGV2YXRvciBjb25uZWN0cyB0aGUgcmlnaHQgZW5kIG9mIGEgdHVubmVsIHRvIHRoZSBsZWZ0IGVuZCBvZiBhbm90aGVyIHR1bm5lbC4gRnVydGhlcm1vcmUsIHRoZSBjb25uZWN0ZWQgY2hhaW4gb2YgdHVubmVscyBhbmQgZWxldmF0b3JzIHNob3VsZCBiZSBtb25vdG9uZSB0byB0aGUgZ3JvdW5kLCBpLmUuLCB3aGVuIG9uZSB0cmF2ZXJzZXMgdGhlIGNoYWluIGZyb20gdGhlIGxlZnRtb3N0IGVuZCBvZiB0aGUgdHVubmVscyB0byB0aGUgcmlnaHRtb3N0IGVuZCBvZiB0aGUgdHVubmVscywgb25lIHBhc3NlcyB0aHJvdWdoIGFsbCB0aGUgdHVubmVscyB3aXRob3V0IGdvaW5nIGJhY2sgdG8gdGhlIGxlZnQuJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkR1ZSB0byB0aGUgbGltaXQgb2YgdGhlIGJ1ZGdldCwgd2UgY2FuIGNvbnN0cnVjdCBhdCBtb3N0IGsgaG9yaXpvbnRhbCB0dW5uZWxzIGZvciBzb21lIHBvc2l0aXZlIGludGVnZXIgay4gVGh1cyBhdCBtb3N0IGstMSB2ZXJ0aWNhbCBlbGV2YXRvcnMgY29ubmVjdGluZyB0aGVtIGFyZSB1c2VkLiBXZSBub3cgY29uc3RydWN0IGFuIGFkZGl0aW9uYWwgdmVydGljYWwgdHVubmVsIGNvbm5lY3RpbmcgZWFjaCBtZXRhbCB0byB0aGUgaG9yaXpvbnRhbCB0dW5uZWxzLiBUaGUgZGlnZ2luZyBjb3N0IG9mIGEgbWV0YWwgaXMgZGVmaW5lZCBhcyBpdHMgdmVydGljYWwgZGlzdGFuY2UgZnJvbSB0aGUgaG9yaXpvbnRhbCB0dW5uZWwuIFRoZSBkaWdnaW5nIGNvc3QgZm9yIG4gbWV0YWxzIGlzIGRlZmluZWQgYXMgdGhlIG1heGltdW0gZGlnZ2luZyBjb3N0IG9mIHRoZSBtZXRhbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWV0YWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzYxcHg7IG9wYWNpdHk6MC45OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6NjcwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEuIEEgZGlnZ2luZyBwbGFuIGZvciAxNSBtZXRhbHMgZm9yIGs9My4gVGhlIHZlcnRpY2FsIGRpc3RhbmNlIGZyb20gdGhlIHJpZ2h0bW9zdCBob3Jpem9udGFsIHR1bm5lbCB0byB0aGUgbG93ZXN0IG1ldGFsIGlzIHRoZSBtYXhpbXVtIGRpc3RhbmNlIGluIHRoaXMgcGxhbiwgd2hpY2ggZGV0ZXJtaW5lcyB0aGUgZGlnZ2luZyBjb3N0IGZvciB0aGUgbWV0YWxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Nb3JlIGZvcm1hbGx5LCBhcyBpbiBGaWd1cmUgMSwgZWFjaCBtZXRhbCBpcyByZXByZXNlbnRlZCBhcyBhIHBvaW50IGluIHRoZSB0d28gZGltZW5zaW9uYWwgcGxhbmUsIGEgaG9yaXpvbnRhbCB0dW5uZWwgYXMgYSBob3Jpem9udGFsIGxpbmUgc2VnbWVudCwgYSB2ZXJ0aWNhbCB0dW5uZWwgYXMgYSB2ZXJ0aWNhbCBsaW5lIHNlZ21lbnQsIGFuZCBhbiBlbGV2YXRvciBhcyBhIHZlcnRpY2FsIGxpbmUgc2VnbWVudC4gWW91IGFyZSBnaXZlbiBhIHNldCBvZiBuIHBvaW50cywge3A8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgLi4uLCBwPHN1Yj5uPFwvc3ViPn0sIHdoZXJlIHA8c3ViPmk8XC9zdWI+IGhhcyB4LWNvb3JkaW5hdGUgeDxzdWI+aTxcL3N1Yj4gYW5kIHktY29vcmRpbmF0ZSB5PHN1Yj5pPFwvc3ViPiwgYW5kIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIGssIHRoZSBtYXhpbXVtIG51bWJlciBvZiBob3Jpem9udGFsIHR1bm5lbHMuIFRoZSBkaWdnaW5nIGNvc3Qgb2YgYSBtZXRhbCBwPHN1Yj5pPFwvc3ViPiwgY29zdChwPHN1Yj5pPFwvc3ViPiksIGlzIHRoZSB2ZXJ0aWNhbCBkaXN0YW5jZSB0byB0aGUgaG9yaXpvbnRhbCB0dW5uZWxzLiBUaGUgZGlnZ2luZyBjb3N0IG9mIFAgPSB7cDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4sIHA8c3ViPm48XC9zdWI+fSwgY29zdChQKSwgaXMgZGVmaW5lZCBhcyB0aGUgbWF4aW11bSBjb3N0IG9mIGNvc3QocDxzdWI+aTxcL3N1Yj4pIG92ZXIgYWxsIGksIGkuZS4sIGNvc3QoUCkgPSBtYXg8c3ViPjEmbGU7aSZsZTtuPFwvc3ViPmNvc3QocDxzdWI+aTxcL3N1Yj4pLiBUaGUgZ29hbCBpcyB0byBkZXRlcm1pbmUgdGhlIHBvc2l0aW9uIG9mIChhdCBtb3N0KSBrIGhvcml6b250YWwgdHVubmVscyBzdWNoIHRoYXQgY29zdChQKSBpcyBtaW5pbWl6ZWQuJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkdpdmVuIGEgc2V0IFAgb2YgbiBwb2ludHMgYW5kIGEgcG9zaXRpdmUgaW50ZWdlciBrLCB5b3Ugd3JpdGUgYSBwcm9ncmFtIHRvIGNvbXB1dGUgdGhlIG1pbmltdW0gdmFsdWUgb2YgY29zdChQKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBuICgyICZsZTsgbiAmbGU7IDEwLDAwMCkgYW5kIGssIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBwb2ludHMgKG1ldGFscykgYW5kIGsgaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIGhvcml6b250YWwgdHVubmVscyB0byBiZSB1c2VkLiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIDJuIGludGVnZXJzLCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KSwgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPiksIC4uLiwgKHg8c3ViPm48XC9zdWI+LCB5PHN1Yj5uPFwvc3ViPiksIHdoaWNoIHJlc3BlY3RpdmVseSByZXByZXNlbnQgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBwb2ludHMgcDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4sIHA8c3ViPm48XC9zdWI+LCBhbmQgLTEwMCwwMDAsMDAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMTAwLDAwMCwwMDAgZm9yIGVhY2ggaS4gVHdvIG5laWdoYm9yaW5nIGNvb3JkaW5hdGVzIGFyZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIE5vdGUgdGhhdCBubyB0d28gcG9pbnRzIGhhdmUgdGhlIHNhbWUgeC1jb29yZGluYXRlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIG1pbmltdW0gdmFsdWUgb2YgY29zdChQKS4gWW91ciBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBmaXJzdCBkaWdpdCBhZnRlciB0aGUgZGVjaW1hbCBwb2ludCwgcm91bmRlZCBvZmYgZnJvbSB0aGUgc2Vjb25kIGRpZ2l0LiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2013 F번