시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 1108 261 166 20.907%

문제

매우 드물고 비싼 금속을 지하에서 찾아냈다. 금속은 땅 속에 넓게 흩어져 있기 때문에 신중하게 채굴 계획을 세우려고 한다. 따라서, 그림 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+XHVjNjA4XHVjMGIwXHVjNzc0IFx1YzgxY1x1ZDU1Y1x1YjQxOFx1YzViNCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyMThcdWQzYzkgXHVkMTMwXHViMTEwXHVjNzQ0IGtcdWFjMWNcdWI5Y2MgXHViOWNjXHViNGU0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gKGtcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCkgXHViNTMwXHViNzdjXHVjMTFjLCBcdWMyMThcdWQzYzkgXHVkMTMwXHViMTEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU2MCBcdWMyMThcdWM5YzEgXHVjNWQ4XHViOWFjXHViY2EwXHVjNzc0XHVkMTMwXHViMjk0IFx1Y2Q1Y1x1YjMwMCBrLTFcdWFjMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzgxYywgXHVjMjE4XHVkM2M5IFx1ZDEzMFx1YjExMFx1YWNmYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVhZTA4XHVjMThkXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM5YzEgXHVkMTMwXHViMTEwXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWFlMDhcdWMxOGRcdWM3NDQgXHVjYzQ0XHVhZDc0XHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgXHVjMjE4XHVkM2M5IFx1ZDEzMFx1YjExMFx1YWNmY1x1Yzc1OCBcdWMyMThcdWM5YzEgXHVhYzcwXHViOWFjXHVjNzc0XHViMmU0LiBcdWFlMDhcdWMxOGQgblx1YWMxY1x1Yjk3YyBcdWNjNDRcdWFkNzRcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWFjMDEgXHVhZTA4XHVjMThkXHVjNzU4IFx1Y2M0NFx1YWQ3NCBcdWJlNDRcdWM2YTkgXHVjOTExIFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWV0YWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzYxcHg7IHdpZHRoOjY3MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAxLiBcdWFlMDhcdWMxOGRcdWM3NzQgMTVcdWFjMWMsIGs9M1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjYzQ0XHVhZDc0IFx1YWNjNFx1ZDY4ZC4gXHVjNzc0IFx1YWNjNFx1ZDY4ZFx1YzVkMFx1YzExYyBcdWNkNWNcdWIzMDAgXHVhYzcwXHViOWFjXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJlNjhcdWFjMDRcdWMwYzlcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDFjIFx1YWM3MFx1YjlhY1x1Yzc3NFx1YWNlMCwgXHVhZGY4IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWM3NzQgXHVhY2M0XHVkNjhkXHVjNzU4IFx1Y2M0NFx1YWQ3NCBcdWJlNDRcdWM2YTlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliYyAxXHVhY2ZjIFx1YWMxOVx1Yzc3NCwgXHVhYzAxIFx1YWUwOFx1YzE4ZFx1Yzc0MCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM3NTggXHVjODEwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWMyMThcdWQzYzkgXHVkMTMwXHViMTEwXHVjNzQwIFx1YzIxOFx1ZDNjOVx1YzEyMCwgXHVjMjE4XHVjOWMxIFx1ZDEzMFx1YjExMFx1YWNmYyBcdWM1ZDhcdWI5YWNcdWJjYTBcdWM3NzRcdWQxMzBcdWIyOTQgXHVjMjE4XHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM4MTAgblx1YWMxYyBQID0ge3A8c3ViPjE8XC9zdWI+LCBwPHN1Yj4yPFwvc3ViPiwgLi4uLCBwPHN1Yj5uPFwvc3ViPn1cdWM2NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhZTA4XHVjMThkIHA8c3ViPmk8XC9zdWI+XHViOTdjIFx1Y2M0NFx1YWQ3NFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViZTQ0XHVjNmE5IGNvc3QocDxzdWI+aTxcL3N1Yj4pXHVjNzQwIFx1YzIxOFx1ZDNjOSBcdWQxMzBcdWIxMTBcdWFjZmMgXHViNWE4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzljMSBcdWFjNzBcdWI5YWNcdWM3NzRcdWIyZTQuIFAgPSB7cDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4gcDxzdWI+bjxcL3N1Yj59XHVjNzU4IFx1Y2M0NFx1YWQ3NCBcdWJlNDRcdWM2YTkgY29zdChQKVx1YjI5NCBcdWJhYThcdWI0ZTAgY29zdChQPHN1Yj5pPFwvc3ViPilcdWM5MTEgXHVjZDVjXHViMzAwXHVhYzEyIChtYXg8c3ViPjEmbGU7aSZsZTtuPFwvc3ViPmNvc3QocDxzdWI+aTxcL3N1Yj4pKSBcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIGNvc3QoUClcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCAoXHVjZDVjXHViMzAwKSBrXHVhYzFjIFx1YzIxOFx1ZDNjOSBcdWQxMzBcdWIxMTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YWNiMFx1YzgxNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxMCBuXHVhYzFjXHVjNzU4IFx1YzlkMVx1ZDU2OSBQXHVjNjQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBjb3N0KFApXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwKFx1YWUwOFx1YzE4ZClcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWFjZmMga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgbiAmbGU7IDEwLDAwMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTAgcDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4sIHA8c3ViPm48XC9zdWI+XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IDJuXHVhYzFjICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pLCAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KSwgLi4uLCAoeDxzdWI+bjxcL3N1Yj4sIHk8c3ViPm48XC9zdWI+KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTAwLDAwMCwwMDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAsMDAwLDAwMCkgXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHViNDUwIFx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgeFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFjMTZcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBjb3N0KFApXHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWMxOGNcdWMyMThcdWM4MTAgXHViNDU4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWJjMThcdWM2MmNcdWI5YmNcdWQ1NzRcdWMxMWMgXHVjY2FiXHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTQ2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1ldGFsIiwiZGVzY3JpcHRpb24iOiI8cD5XZSBmb3VuZCByYXJlIGFuZCB2YWx1YWJsZSBtZXRhbHMgdW5kZXIgdGhlIGdyb3VuZC4gVGhlIG1ldGFscyBhcmUgd2lkZWx5IHNjYXR0ZXJlZCB1bmRlcmdyb3VuZCwgc28gd2UgbmVlZCBhIGNhcmVmdWwgcGxhbiB0byBkaWcgdGhlbS4gRm9yIHRoaXMsIHdlIGFyZSBnb2luZyB0byBidWlsZCBhIG51bWJlciBvZiBob3Jpem9udGFsIHR1bm5lbHMgY29ubmVjdGVkIGJ5IHZlcnRpY2FsIGVsZXZhdG9ycywgYXMgaW4gRmlndXJlIDEuIEV2ZXJ5IHZlcnRpY2FsIGVsZXZhdG9yIGNvbm5lY3RzIHRoZSByaWdodCBlbmQgb2YgYSB0dW5uZWwgdG8gdGhlIGxlZnQgZW5kIG9mIGFub3RoZXIgdHVubmVsLiBGdXJ0aGVybW9yZSwgdGhlIGNvbm5lY3RlZCBjaGFpbiBvZiB0dW5uZWxzIGFuZCBlbGV2YXRvcnMgc2hvdWxkIGJlIG1vbm90b25lIHRvIHRoZSBncm91bmQsIGkuZS4sIHdoZW4gb25lIHRyYXZlcnNlcyB0aGUgY2hhaW4gZnJvbSB0aGUgbGVmdG1vc3QgZW5kIG9mIHRoZSB0dW5uZWxzIHRvIHRoZSByaWdodG1vc3QgZW5kIG9mIHRoZSB0dW5uZWxzLCBvbmUgcGFzc2VzIHRocm91Z2ggYWxsIHRoZSB0dW5uZWxzIHdpdGhvdXQgZ29pbmcgYmFjayB0byB0aGUgbGVmdC4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuRHVlIHRvIHRoZSBsaW1pdCBvZiB0aGUgYnVkZ2V0LCB3ZSBjYW4gY29uc3RydWN0IGF0IG1vc3QgayBob3Jpem9udGFsIHR1bm5lbHMgZm9yIHNvbWUgcG9zaXRpdmUgaW50ZWdlciBrLiBUaHVzIGF0IG1vc3Qgay0xIHZlcnRpY2FsIGVsZXZhdG9ycyBjb25uZWN0aW5nIHRoZW0gYXJlIHVzZWQuIFdlIG5vdyBjb25zdHJ1Y3QgYW4gYWRkaXRpb25hbCB2ZXJ0aWNhbCB0dW5uZWwgY29ubmVjdGluZyBlYWNoIG1ldGFsIHRvIHRoZSBob3Jpem9udGFsIHR1bm5lbHMuIFRoZSBkaWdnaW5nIGNvc3Qgb2YgYSBtZXRhbCBpcyBkZWZpbmVkIGFzIGl0cyB2ZXJ0aWNhbCBkaXN0YW5jZSBmcm9tIHRoZSBob3Jpem9udGFsIHR1bm5lbC4gVGhlIGRpZ2dpbmcgY29zdCBmb3IgbiBtZXRhbHMgaXMgZGVmaW5lZCBhcyB0aGUgbWF4aW11bSBkaWdnaW5nIGNvc3Qgb2YgdGhlIG1ldGFscy4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tZXRhbC5wbmdcIiBzdHlsZT1cImhlaWdodDozNjFweDsgb3BhY2l0eTowLjk7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDo2NzBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gQSBkaWdnaW5nIHBsYW4gZm9yIDE1IG1ldGFscyBmb3Igaz0zLiBUaGUgdmVydGljYWwgZGlzdGFuY2UgZnJvbSB0aGUgcmlnaHRtb3N0IGhvcml6b250YWwgdHVubmVsIHRvIHRoZSBsb3dlc3QgbWV0YWwgaXMgdGhlIG1heGltdW0gZGlzdGFuY2UgaW4gdGhpcyBwbGFuLCB3aGljaCBkZXRlcm1pbmVzIHRoZSBkaWdnaW5nIGNvc3QgZm9yIHRoZSBtZXRhbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1vcmUgZm9ybWFsbHksIGFzIGluIEZpZ3VyZSAxLCBlYWNoIG1ldGFsIGlzIHJlcHJlc2VudGVkIGFzIGEgcG9pbnQgaW4gdGhlIHR3byBkaW1lbnNpb25hbCBwbGFuZSwgYSBob3Jpem9udGFsIHR1bm5lbCBhcyBhIGhvcml6b250YWwgbGluZSBzZWdtZW50LCBhIHZlcnRpY2FsIHR1bm5lbCBhcyBhIHZlcnRpY2FsIGxpbmUgc2VnbWVudCwgYW5kIGFuIGVsZXZhdG9yIGFzIGEgdmVydGljYWwgbGluZSBzZWdtZW50LiBZb3UgYXJlIGdpdmVuIGEgc2V0IG9mIG4gcG9pbnRzLCB7cDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4sIHA8c3ViPm48XC9zdWI+fSwgd2hlcmUgcDxzdWI+aTxcL3N1Yj4gaGFzIHgtY29vcmRpbmF0ZSB4PHN1Yj5pPFwvc3ViPiBhbmQgeS1jb29yZGluYXRlIHk8c3ViPmk8XC9zdWI+LCBhbmQgdGhlIHBvc2l0aXZlIGludGVnZXIgaywgdGhlIG1heGltdW0gbnVtYmVyIG9mIGhvcml6b250YWwgdHVubmVscy4gVGhlIGRpZ2dpbmcgY29zdCBvZiBhIG1ldGFsIHA8c3ViPmk8XC9zdWI+LCBjb3N0KHA8c3ViPmk8XC9zdWI+KSwgaXMgdGhlIHZlcnRpY2FsIGRpc3RhbmNlIHRvIHRoZSBob3Jpem9udGFsIHR1bm5lbHMuIFRoZSBkaWdnaW5nIGNvc3Qgb2YgUCA9IHtwPHN1Yj4xPFwvc3ViPiwgcDxzdWI+MjxcL3N1Yj4sIC4uLiwgcDxzdWI+bjxcL3N1Yj59LCBjb3N0KFApLCBpcyBkZWZpbmVkIGFzIHRoZSBtYXhpbXVtIGNvc3Qgb2YgY29zdChwPHN1Yj5pPFwvc3ViPikgb3ZlciBhbGwgaSwgaS5lLiwgY29zdChQKSA9IG1heDxzdWI+MSZsZTtpJmxlO248XC9zdWI+Y29zdChwPHN1Yj5pPFwvc3ViPikuIFRoZSBnb2FsIGlzIHRvIGRldGVybWluZSB0aGUgcG9zaXRpb24gb2YgKGF0IG1vc3QpIGsgaG9yaXpvbnRhbCB0dW5uZWxzIHN1Y2ggdGhhdCBjb3N0KFApIGlzIG1pbmltaXplZC4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuR2l2ZW4gYSBzZXQgUCBvZiBuIHBvaW50cyBhbmQgYSBwb3NpdGl2ZSBpbnRlZ2VyIGssIHlvdSB3cml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB0aGUgbWluaW11bSB2YWx1ZSBvZiBjb3N0KFApLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gcG9zaXRpdmUgaW50ZWdlcnMsIG4gKDIgJmxlOyBuICZsZTsgMTAsMDAwKSBhbmQgaywgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIHBvaW50cyAobWV0YWxzKSBhbmQgayBpcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgaG9yaXpvbnRhbCB0dW5uZWxzIHRvIGJlIHVzZWQuIFRoZSBuZXh0IGxpbmUgY29udGFpbnMgMm4gaW50ZWdlcnMsICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pLCAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KSwgLi4uLCAoeDxzdWI+bjxcL3N1Yj4sIHk8c3ViPm48XC9zdWI+KSwgd2hpY2ggcmVzcGVjdGl2ZWx5IHJlcHJlc2VudCB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHBvaW50cyBwPHN1Yj4xPFwvc3ViPiwgcDxzdWI+MjxcL3N1Yj4sIC4uLiwgcDxzdWI+bjxcL3N1Yj4sIGFuZCAtMTAwLDAwMCwwMDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAsMDAwLDAwMCBmb3IgZWFjaCBpLiBUd28gbmVpZ2hib3JpbmcgY29vcmRpbmF0ZXMgYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gTm90ZSB0aGF0IG5vIHR3byBwb2ludHMgaGF2ZSB0aGUgc2FtZSB4LWNvb3JkaW5hdGVzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbWluaW11bSB2YWx1ZSBvZiBjb3N0KFApLiBZb3VyIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIGZpcnN0IGRpZ2l0IGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LCByb3VuZGVkIG9mZiBmcm9tIHRoZSBzZWNvbmQgZGlnaXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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