whx的加油站

题目描述:

老司机whx所在的国家里有n个城市，不妨把这些城市看做一些坐标系上的点。一天，whx想开车走遍整个国家并最终回家。但是whx的车不那么给力，加了一次油的情况下只能走不超过D米，显然在他的车用完油之前必须得加油，不然就回不了家找妹子玩了。因为老司机whx在这个国家里非常出名，所以他可以在任意城市建立加油站。城市1是必须得建加油站的，因为whx就住在城市1。在编号为i的城市建立加油站需要花费2i−1元，城市从1开始编号。 
    whx想要花最小的代价建立加油站以满足他走遍所有城市的要求，请你求出这个代价。

输入格式:

多组数据，不超过30组。 
    每组数据第一行两个整数n,D(n≤128,0≤D≤109)，分别表示城市个数和每次加完油之后whx最多能走多少米。 
    接下来n行每行两个整数x,y,(0≤x,y≤1000)，表示第i个城市的坐标。 
    第i个城市和第j个城市之间的距离是⌈√(xi−xj)2+(yi−yj)2⌉，其中⌈⌉表示向上取整。 

输出格式:

对于每组数据，以二进制的形式输出最小代价，没有前导零。如果不可能，则输出-1。

样例输入:

3 3
0 0
0 3
0 1

3 2
0 0
0 3
0 1

3 1
0 0
0 3
0 1

16 23
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69

样例输出:

11
111
-1
10111011

提示:

样例解释
第一个样例中，应在(0,0)和(0,3)建加油站。走的顺序是1->3->2->3->1，花费是21−1+22−1=3。 
 
数据范围 
数据采用捆绑测试。 
Subtask 1(30pts) 
n≤8 
Subtask 2(70pts) 
n≤128

时间限制: 1000ms
空间限制: 256MB

---