
ZOJ Problem Set  3136
We have n test tubes {t} containing different liquid chemicals. And we have M mg(milligram) of another i chemical C in a beaker. If we put x mg of Cinto a test tube t_{i}, then G (a sort of gas) is produced in t_{i}. The amount of G produced in each t is determined by a linear tube function f(x_{i}) = a_{i} * x_{i} + b_{i} (unit is mg), where x_{i} is the amount of C put into t_{i}. Note that we can only measure integer amount of C, and so every x_{i} should be an integer. Assume that f_{3}(x) = 3 * x+ 2 for test tube t_{3}. If we put x=40 mg of C into t_{3} , then 122 mg of G is produced. This experiment has a requirement, that is, we must equalize the amount of G produced in every t_{i} by carefully distributing Mover all n tubes, that is x_{1} + x_{2} + ... + x_{n}= M. For example, if we have only three test tubes with tube functions f_{1}(x) = 3 * x + 5 , f_{2}(x) = 4 * x + 3 , f_{3}(x) = 1 * x + 7 and M= 27, then we can make 23 mg of G in each tube by assigning x_{1} = 6, x_{2} = 5, x_{3} = 16. But it is impossible to equalize the amount of G produced in each tube if we are given M = 26. Input Your program is to read from standard input. The input consists of Ttest cases. The number of test cases T is given in the first line of the input. Each testcase starts with a line containing an integer n < 20, the number of integer pairs, a_{i} and b_{i}. A pair of two integers, a_{i} and b_{i} , is given in the following n lines. And finally M, the initial amount of C is given in the next line. There is at least a single space between a_{i}and b_{i}, where 1 <= a_{i} <= 10 and 1 <= b_{i} <= 1,000. And M is a positive integer less than 10,000. Output Your program is to write to standard output. Print exactly one line for each test case. Print the amount of G produced in each tube, if it is possible to equalize the amount of in each tube. Print 0, if it is impossible to equalize the amount of G in each tube. Sample Input3 3 3 5 4 3 1 7 27 3 3 5 4 3 1 7 26 8 2 156 2 2 2 216 4 12 3 24 5 36 1 96 3 6 695Sample Output 23 0 276 Source: Asia Regional Contest Seoul 2006 