8953번 - Gas 다국어채점 준비 중

We have n test tubes {t_i} containing different liquid chemicals. And we have M mg (milligram) of another chemical C in a beaker. If we put x mg of C into a test tube t_i, then G (a sort of gas) is produced in t_i. The amount of G produced in each t_i 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₃(x)=3•x+2 for test tube t₃. If we put x=40 mg of C into t₃, 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 M over all n tubes, that is x₁+x₂+...+x_n=M.

For example, if we have only three test tubes with tube functions  f₁(x)=3•x+5,  f₂(x)=4•x+3,  f₃(x)=1•x+7 and M = 27, then we can make 23 mg of G in each tube by assigning x₁=6, x₂=5, x₃=16. But it is impossible to equalize the amount of G produced in each tube if we are given M = 26. 

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case 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 ≤ 1000. And M is a positive integer less than 10,000.

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.

The following shows sample input and output for three test cases.