Judges' response

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

  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.

Input

  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)

Output

  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.

Sample Input

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

Sample Output

1 6 2 8 -1 -1 8 467

Hint

liuyiding

Source

2012 ACM/ICPC Asia Regional Tianjin Online

提交代码