시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 52 22 17 45.946%

문제

화학 제국의 왕 성준이는 계속되는 이웃나라의 침범으로부터 자유로워지기 위해 자국의 자랑 화학 방벽을 건설하기로 마음먹었다. 이 방벽은 근처에 다가오는 생명체에게 해로운 독성을 내뿜어서 더이상 다른 나라들이 얼씬도 못하게 만들 것이다!

그러나 이 방벽은 만들기 까다롭기에 가능한 한 적게 지어야 하며, 자국민들에게도 악영향을 끼칠 수 있으므로 자국의 모든 건물들로부터 L 이상의 거리를 유지해야만 한다.

자국의 건물들의 좌표가 주어졌을 때, 모든 건물들로부터 L 이상의 거리를 두면서 모든 건물을 한번에 두르는 방벽의 최소 길이를 구하시오.

입력

첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000)

다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌표는 다르며, 건물은 충분히 작아서 점과 같다고 생각해도 좋다. 방벽은 자신들끼리 교차해서는 안 되며 끊어져서도 안 된다.

출력

첫째 줄에 답을 정수 단위로 반올림하여 출력한다.

예제 입력 1

9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200

예제 출력 1

1628
W3sicHJvYmxlbV9pZCI6Ijc0MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZjlcdWIzYzUgXHViYzI5XHViY2JkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2NTRcdWQ1NTkmbmJzcDtcdWM4MWNcdWFkNmRcdWM3NTggXHVjNjU1IFx1YzEzMVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWFjYzRcdWMxOGRcdWI0MThcdWIyOTQgXHVjNzc0XHVjNmMzXHViMDk4XHViNzdjXHVjNzU4IFx1Y2U2OFx1YmM5NFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM3OTBcdWM3MjBcdWI4NWNcdWM2Y2NcdWM5YzBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Yzc5MFx1YWQ2ZFx1Yzc1OCBcdWM3OTBcdWI3OTEgPHN0cm9uZz5cdWQ2NTRcdWQ1NTkgXHViYzI5XHViY2JkPFwvc3Ryb25nPlx1Yzc0NCBcdWFjNzRcdWMxMjRcdWQ1NThcdWFlMzBcdWI4NWMgXHViOWM4XHVjNzRjXHViYTM5XHVjNWM4XHViMmU0LiBcdWM3NzQgXHViYzI5XHViY2JkXHVjNzQwIFx1YWRmY1x1Y2M5OFx1YzVkMCBcdWIyZTRcdWFjMDBcdWM2MjRcdWIyOTQgXHVjMGRkXHViYTg1XHVjY2I0XHVjNWQwXHVhYzhjIFx1ZDU3NFx1Yjg1Y1x1YzZiNCBcdWIzYzVcdWMxMzFcdWM3NDQgXHViMGI0XHViZmRjXHVjNWI0XHVjMTFjIFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWIyZTRcdWI5NzggXHViMDk4XHViNzdjXHViNGU0XHVjNzc0IFx1YzViY1x1YzUyY1x1YjNjNCBcdWJhYmJcdWQ1NThcdWFjOGMgXHViOWNjXHViNGU0IFx1YWM4M1x1Yzc3NFx1YjJlNCE8XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2VjXHViMDk4IFx1Yzc3NCBcdWJjMjlcdWJjYmRcdWM3NDAgXHViOWNjXHViNGU0XHVhZTMwIFx1YWU0Y1x1YjJlNFx1Yjg2ZFx1YWUzMFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkNTVjIFx1YzgwMVx1YWM4YyBcdWM5YzBcdWM1YjRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWM3OTBcdWFkNmRcdWJiZmNcdWI0ZTRcdWM1ZDBcdWFjOGNcdWIzYzQgXHVjNTQ1XHVjNjAxXHVkNWE1XHVjNzQ0IFx1YjA3Y1x1Y2U2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIFx1Yzc5MFx1YWQ2ZFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhYzc0XHViYjNjXHViNGU0XHViODVjXHViZDgwXHVkMTMwIEwgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM3MjBcdWM5YzBcdWQ1NzRcdWM1N2NcdWI5Y2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWFkNmRcdWM3NTggXHVhYzc0XHViYjNjXHViNGU0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVhYzc0XHViYjNjXHViNGU0XHViODVjXHViZDgwXHVkMTMwIEwgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWI0NTBcdWJhNzRcdWMxMWMgXHViYWE4XHViNGUwJm5ic3A7XHVhYzc0XHViYjNjXHVjNzQ0IFx1ZDU1Y1x1YmM4OFx1YzVkMCZuYnNwO1x1YjQ1MFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWJjYmRcdWM3NTggXHVjZDVjXHVjMThjIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjNzRcdWJiM2NcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVhYzcwXHViOWFjIExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygzICZsZTsgTiAmbGU7IDEwMDAsJm5ic3A7MSAmbGU7IEwgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzcwXHVjY2QwIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWM4OGNcdWQ0NWMgWDxzdWI+aTxcL3N1Yj5cdWM2NDAgWTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoLTEwMDAwICZsZTsgWDxzdWI+aTxcL3N1Yj4sIFk8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyAxMDAwMCkgXHViYWE4XHViNGUwIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHViMmU0XHViOTc0XHViYTcwLCBcdWFjNzRcdWJiM2NcdWM3NDAgXHVjZGE5XHViZDg0XHVkNzg4IFx1Yzc5MVx1YzU0NFx1YzExYyBcdWM4MTBcdWFjZmMgXHVhYzE5XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YjNjNCBcdWM4OGJcdWIyZTQuIFx1YmMyOVx1YmNiZFx1Yzc0MCBcdWM3OTBcdWMyZTBcdWI0ZTRcdWIwN2NcdWI5YWMgXHVhZDUwXHVjYzI4XHVkNTc0XHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MThcdWJhNzAgXHViMDRhXHVjNWI0XHVjODM4XHVjMTFjXHViM2M0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZjVcdWM3NDQgXHVjODE1XHVjMjE4IFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWJjMThcdWM2MmNcdWI5YmNcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc0MjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXYWxsIiwiZGVzY3JpcHRpb24iOiI8cD5PbmNlIHVwb24gYSB0aW1lIHRoZXJlIHdhcyBhIGdyZWVkeSBLaW5nIHdobyBvcmRlcmVkIGhpcyBjaGllZiBBcmNoaXRlY3QgdG8gYnVpbGQgYSB3YWxsIGFyb3VuZCB0aGUgS2luZyYjMzk7cyBjYXN0bGUuIFRoZSBLaW5nIHdhcyBzbyBncmVlZHksIHRoYXQgaGUgd291bGQgbm90IGxpc3RlbiB0byBoaXMgQXJjaGl0ZWN0JiMzOTtzIHByb3Bvc2FscyB0byBidWlsZCBhIGJlYXV0aWZ1bCBicmljayB3YWxsIHdpdGggYSBwZXJmZWN0IHNoYXBlIGFuZCBuaWNlIHRhbGwgdG93ZXJzLiBJbnN0ZWFkLCBoZSBvcmRlcmVkIHRvIGJ1aWxkIHRoZSB3YWxsIGFyb3VuZCB0aGUgd2hvbGUgY2FzdGxlIHVzaW5nIHRoZSBsZWFzdCBhbW91bnQgb2Ygc3RvbmUgYW5kIGxhYm9yLCBidXQgZGVtYW5kZWQgdGhhdCB0aGUgd2FsbCBzaG91bGQgbm90IGNvbWUgY2xvc2VyIHRvIHRoZSBjYXN0bGUgdGhhbiBhIGNlcnRhaW4gZGlzdGFuY2UuIElmIHRoZSBLaW5nIGZpbmRzIHRoYXQgdGhlIEFyY2hpdGVjdCBoYXMgdXNlZCBtb3JlIHJlc291cmNlcyB0byBidWlsZCB0aGUgd2FsbCB0aGFuIGl0IHdhcyBhYnNvbHV0ZWx5IG5lY2Vzc2FyeSB0byBzYXRpc2Z5IHRob3NlIHJlcXVpcmVtZW50cywgdGhlbiB0aGUgQXJjaGl0ZWN0IHdpbGwgbG9vc2UgaGlzIGhlYWQuIE1vcmVvdmVyLCBoZSBkZW1hbmRlZCBBcmNoaXRlY3QgdG8gaW50cm9kdWNlIGF0IG9uY2UgYSBwbGFuIG9mIHRoZSB3YWxsIGxpc3RpbmcgdGhlIGV4YWN0IGFtb3VudCBvZiByZXNvdXJjZXMgdGhhdCBhcmUgbmVlZGVkIHRvIGJ1aWxkIHRoZSB3YWxsLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gaGVscCBwb29yIEFyY2hpdGVjdCB0byBzYXZlIGhpcyBoZWFkLCBieSB3cml0aW5nIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZmluZCB0aGUgbWluaW11bSBwb3NzaWJsZSBsZW5ndGggb2YgdGhlIHdhbGwgdGhhdCBoZSBjb3VsZCBidWlsZCBhcm91bmQgdGhlIGNhc3RsZSB0byBzYXRpc2Z5IEtpbmcmIzM5O3MgcmVxdWlyZW1lbnRzLjxcL3A+XHJcblxyXG48cD5UaGUgdGFzayBpcyBzb21ld2hhdCBzaW1wbGlmaWVkIGJ5IHRoZSBmYWN0LCB0aGF0IHRoZSBLaW5nJiMzOTtzIGNhc3RsZSBoYXMgYSBwb2x5Z29uYWwgc2hhcGUgYW5kIGlzIHNpdHVhdGVkIG9uIGEgZmxhdCBncm91bmQuIFRoZSBBcmNoaXRlY3QgaGFzIGFscmVhZHkgZXN0YWJsaXNoZWQgYSBDYXJ0ZXNpYW4gY29vcmRpbmF0ZSBzeXN0ZW0gYW5kIGhhcyBwcmVjaXNlbHkgbWVhc3VyZWQgdGhlIGNvb3JkaW5hdGVzIG9mIGFsbCBjYXN0bGUmIzM5O3MgdmVydGljZXMgaW4gZmVldC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHR3byBpbnRlZ2VyIG51bWJlcnMgTiBhbmQgTCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gTiAoMyAmbGU7IE4gJmxlOyAxMDAwKSBpcyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBLaW5nJiMzOTtzIGNhc3RsZSwgYW5kIEwgKDEgJmxlOyBMICZsZTsgMTAwMCkgaXMgdGhlIG1pbmltYWwgbnVtYmVyIG9mIGZlZXQgdGhhdCBLaW5nIGFsbG93cyBmb3IgdGhlIHdhbGwgdG8gY29tZSBjbG9zZSB0byB0aGUgY2FzdGxlLjxcL3A+XHJcblxyXG48cD5OZXh0IE4gbGluZXMgZGVzY3JpYmUgY29vcmRpbmF0ZXMgb2YgY2FzdGxlJiMzOTtzIHZlcnRpY2VzIGluIGEgY2xvY2t3aXNlIG9yZGVyLiBFYWNoIGxpbmUgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVycyBYPHN1Yj5pPFwvc3ViPiBhbmQgWTxzdWI+aTxcL3N1Yj4gc2VwYXJhdGVkIGJ5IGEgc3BhY2UgKC0xMDAwMCAmbGU7IFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAwKSB0aGF0IHJlcHJlc2VudCB0aGUgY29vcmRpbmF0ZXMgb2YgaXRoIHZlcnRleC4gQWxsIHZlcnRpY2VzIGFyZSBkaWZmZXJlbnQgYW5kIHRoZSBzaWRlcyBvZiB0aGUgY2FzdGxlIGRvIG5vdCBpbnRlcnNlY3QgYW55d2hlcmUgZXhjZXB0IGZvciB2ZXJ0aWNlcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Xcml0ZSB0byB0aGUgb3V0cHV0IGZpbGUgdGhlIHNpbmdsZSBudW1iZXIgdGhhdCByZXByZXNlbnRzIHRoZSBtaW5pbWFsIHBvc3NpYmxlIGxlbmd0aCBvZiB0aGUgd2FsbCBpbiBmZWV0IHRoYXQgY291bGQgYmUgYnVpbHQgYXJvdW5kIHRoZSBjYXN0bGUgdG8gc2F0aXNmeSBLaW5nJiMzOTtzIHJlcXVpcmVtZW50cy4gWW91IG11c3QgcHJlc2VudCB0aGUgaW50ZWdlciBudW1iZXIgb2YgZmVldCB0byB0aGUgS2luZywgYmVjYXVzZSB0aGUgZmxvYXRpbmcgbnVtYmVycyBhcmUgbm90IGludmVudGVkIHlldC4gSG93ZXZlciwgeW91IG11c3Qgcm91bmQgdGhlIHJlc3VsdCBpbiBzdWNoIGEgd2F5LCB0aGF0IGl0IGlzIGFjY3VyYXRlIHRvIDggaW5jaGVzICgxIGZvb3QgaXMgZXF1YWwgdG8gMTIgaW5jaGVzKSwgc2luY2UgdGhlIEtpbmcgd2lsbCBub3QgdG9sZXJhdGUgbGFyZ2VyIGVycm9yIGluIHRoZSBlc3RpbWF0ZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d