There are multiple test cases, the integer on the first line T (T<25) indicates the number of test cases.
Each test case begins with two integers n (<=150), the number of location(including the depot) and m(<=5), the number of different skills.
The next line gives two integers x0, y0 indicates the coordinate of depot.
Then follows n - 1 lines begins with 4 integer numbers: xi, yi, bi(bi>0), pi(pi>0), (xi, yi) gives the coordinate of the i-th location, bi gives the beginning time and pi gives the time cost. The rest of the line gives m non-negative integers v1, v2, ..., vm, of which the i-th number indicates the the number of workers of type i needed (for all vi, 0<=vi<10, each location at least requires one worker).
All integers are less than 1000000 (106).