406827: GYM102566 D Government

In a cool country we can find $$$M$$$ cities. The gods above wish to accomplish $$$N$$$ development projects. Each of the $$$N$$$ projects has two distinct investment schemes. For each of the $$$2 \cdot N$$$ investment schemes we know the respective cost for each of the $$$M$$$ cities. Please note that one of the two investment schemes of each project is seen as harmful in the eyes of public opinion. The exact budget for each of the $$$M$$$ cities was already decided by the Government. Your task is to determine the minimum number of harmful investment schemes which can be selected, such that the total spending for each city to be exactly the budget allocated for it. If it is impossible to spend the exact amount of money allocated for each city you should print out "$$$impossible$$$". Keep in mind that for each of the $$$N$$$ projects you have to pick exactly one of the investment schemes.

The first line of the input will contain the number of test cases $$$T$$$ ($$$1 \leq T \leq 30)$$$. The first line of each test case will contain $$$N$$$ ($$$1 \leq N \leq 30$$$, the number of projects) and $$$M$$$ ($$$1 \leq M \leq 30$$$, the number of cities). The second line of each test case will contain $$$M$$$ integers: $$$b_1, b_2, ..., b_M$$$, the budget allocated to each of the $$$M$$$ cities ($$$0 \leq b_i \leq 2000$$$). The following $$$N$$$ lines of each test case will be structured as follows. For each project $$$i$$$ there will be a line containing $$$M$$$ pairs of integers $$$x_j$$$ ($$$0 \leq x_j \leq 100$$$, the cost of the non-harmful scheme) and $$$y_j$$$ ($$$0 \leq y_j \leq 100$$$, the cost of the harmful scheme) - the two possible costs of the $$$i$$$-th project for the $$$j$$$-th city.

The output should contains $$$T$$$ lines, each containing the answer to a test.

2
3 2
10 5
3 4 2 0
3 1 1 4
1 4 4 2
3 4
2 0 3 2
0 1 1 0 1 1 0 1
2 0 0 0 1 1 1 0
0 2 0 0 1 1 0 1

1
impossible