The contest is running and the judges is busy watching the progress of the contest. Suddenly, N - 1 (N <= 16) contestants hand up their hand at the same time. The judges should go to answer the contestants' question one by one.
The judges already foresee that answering contest i's question would cost Ci minutes. In order to serve all the contestant, each judges is assigned to serve some subset of the contestants. As the judges have limited patience, each one of them can serve the
contestants for no more than M minutes.
　　You are asked to solve two problems:
　　1. At least how many judges should be sent so that they can serve all the contestants? (Because the judges have limited patience, each one of them cannot serve too many contestants.)
　　2. If there are infinite number of judges, how to assign the route for each judge so that the sum of their walking time is minimized? Each contestant i is reside in place (xi, yi), the judges are in place (x1, y1). Assuming
the walking speed of the judge is 1.

　　There are several test cases, Each case begin with two integer N, M(with the meaning in the above context, 2 <= N <= 16, 0 <= M <= 100000).
　　Then N lines follow and line i will contain two numbers x, y(0 <= x, y <= 1000), indicating the coordinate of place i.
　　Then another N lines follow and line i will contain numbers Ci(0 <= Ci <= 1000), indicating the time to solve contestant i's question. C1 will 0 as place 1 is for the judges.
　　
　　The distance between place i and place j is defined as ceil(sqrt((xi - xj) ^ 2 + (yi - yj) ^ 2)). (ceil means rounding the number up, e.g. ceil(4.1) = 5)

　　For each case, output two numbers. The first is the minimum number of judges for question 1. The second is the minimum sum of walking time for question 2.
　　If it's impossible to serve all the contestants, please output -1 -1 instead.

3 3
0 0
0 3
0 1
0
1
2

3 2
0 0
0 3
0 1
0
1
2

3 1
0 0
0 3
0 1
0
1
2
　　
16 35
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
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11

1 6
2 8
-1 -1
8 467

题意：给出n个点，第一个点是裁判的位置，其余n-1个点是任务需要裁判去完成，每个裁判去完成任务总时间不能超过M（不包括走路的时间） ，每个点都有一个坐标和完成这个任务的时间，裁判从一个点到另一个时间所花的时间是两点之间的距离，（1）求完成所有任务最少需要多少个裁判。（2）如果有无数个裁判，要求完成所有的任务所经路程的时间总和最小是多少。（每个裁判最终要回到原来的位置，且最少用到条件（1）得到的裁判个数）。

分析：因为每个裁判做任务总时间不能超过M ，所以用状态压缩把一个裁判能完成的任务找出来，并且记录下来，那么接下来完成第（1）问就好办了，直接DP一下。要想做出第（2）问，那么首先要算出一个裁判去完成的任务状态（必须这种状态一个裁判能完成）的最少用时（不包括返回原来位置的用时），之后再把每个状态以某个点作为结尾点返回到裁判原来的位置的最少用时。再用一个分组背包求出用i 个裁判去完成任务状态 s 花的最少时间，最后就得出结果。

#include<stdio.h>
#include<math.h>

const int N = 1<<16 ;
const int inf= 0xfffffff ;

int dpk[N],dps[N],state[N],k,ok[N];
int map[16][16],routeDist[N][16],dpks[16][N];
double x[16],y[16];
int n,M,c[16];

//------------初始化-------------
void init()
{
    //求出两点之间这距离
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            map[i][j]=ceil(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));

    int tn=n-1 , sumc;
    dpk[0]=0; k=0;
    //算出每个裁判可以完成的任务，用状态压缩
    for(int s=1; s<(1<<tn); s++)
    {
        sumc=0;  ok[s]=0;
        dpk[s]=inf; dps[s]=inf;
        for(int i=0; (1<<i)<=s; i++)
            if(s&(1<<i))
            sumc+=c[i];
        if(sumc<=M) state[k++]=s,ok[s]=1;
    }
}

//----------------计算用无数个裁判去完成n-1个任务花费的最少时间-------------
int min(int a,int b){return a>b?b:a;}
void countRouteDist()
{
    int tn=n-1;
    for(int i=1; i<(1<<tn); i++)
        for(int j=0; j<=tn; j++)
        routeDist[i][j]=inf ,dpks[j][i]=inf;

    for(int i=0; i<tn; i++) //裁判位置到每个点的时间
        routeDist[1<<i][i]=map[n-1][i];

    //计算从裁判的位置通过路径状态 s，并以点 i 结尾的最短时间
    for(int s=1; s<(1<<tn);  s++)
        for(int i=0; (1<<i)<=s; i++)
        if(((1<<i)&s)&&routeDist[s][i]!=inf)
        {
            for(int j=0; j<tn; j++) //跟据routeDist[s][i]去更新 routeDist[s|(1<<j)][j]
                if(!((1<<j)&s)&&ok[s|(1<<j)]) //判断一个人可以完成这种状态
                    routeDist[s|(1<<j)][j] =min(routeDist[s|(1<<j)][j],routeDist[s][i]+map[i][j]);
        }
    for(int s=1; s<(1<<tn);  s++)
    {
        for(int i=0; (1<<i)<=s; i++)
        if(routeDist[s][i]!=inf)
        {
            //裁判完成每种状态后都要回到原来的位置 点 n-1
            routeDist[s][i]+=ceil(sqrt((x[n-1]-x[i])*(x[n-1]-x[i])+(y[n-1]-y[i])*(y[n-1]-y[i])));
            dps[s]=min(dps[s],routeDist[s][i]);  //找出一个人能完成每种状态的最小时间
        }
        dpks[1][s]=dps[s]; //一个人完成状态任务 s 的最小时间
    }

    // 计算每种任务的状态 s 由 i 个人去完成花的最小时间
    for(int i=2; i<=tn; i++) //人数
        for(int j=0; j<k; j++) //一个人可以完成的任务状态数
        for(int s=(1<<tn)-1; s>state[j]; s--) //每种任务的状态
        if((s|state[j])==s&&dpks[i-1][s^state[j]]!=inf)
            dpks[i][s]=min(dpks[i][s],dpks[i-1][s^state[j]]+dps[state[j]]);

}

void zeroOne()
{
    int tn=n-1;
    for(int i=0; i<k ; i++)
        for(int s=(1<<tn)-1; s>=state[i]; s--)
        if((s|state[i])==s)
        {
            if(dpk[s]>dpk[s^state[i]]+1)
                dpk[s]=dpk[s^state[i]]+1;
        }
}
int main()
{
    int flag,MIN;
    while(scanf("%d%d",&n,&M)>0)
    {
        flag=0;

        scanf("%lf%lf",&x[n-1],&y[n-1]);//裁判的位置
        for(int i=0; i<n-1; i++)
            scanf("%lf%lf",&x[i],&y[i]);
        scanf("%d",&c[n-1]); //裁判的
        for(int i=0; i<n-1; i++)
        {
            scanf("%d",&c[i]);
            if(c[i]>M) flag=1;
        }

        if(flag)
        {
            printf("-1 -1\n"); continue;
        }

        init();
        zeroOne();
        countRouteDist();

        n--;
        MIN=inf;
        for(int i=dpk[(1<<n)-1]; i<=n; i++)
        if(dpks[i][(1<<n)-1]<MIN)
            MIN=dpks[i][(1<<n)-1];

        printf("%d %d\n",dpk[(1<<n)-1],MIN);
    }
}