시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

We have n test tubes {ti} 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 ti, then G (a sort of gas) is produced in ti. The amount of G produced in each ti is determined by a linear tube function f(xi)=ai•xi+bi (unit is mg), where xi is the amount of C put into ti. Note that we can only measure integer amount of C, and so every xshould be an integer.

Assume that f3(x)=3•x+2 for test tube t3. If we put x=40 mg of C into t3, then 122 mg of G is produced. This experiment has a requirement, that is, we must equalize the amount of G produced in every tby carefully distributing M over all n tubes, that is x1+x2+...+xn=M.

For example, if we have only three test tubes with tube functions  f1(x)=3•x+5,  f2(x)=4•x+3,  f3(x)=1•x+7 and M = 27, then we can make 23 mg of G in each tube by assigning x1=6, x2=5, x3=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, ai and bi. A pair of two integers, ai and bi, 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 ai and bi, where 1 ≤ ai ≤ 10 and 1 ≤ bi ≤ 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. 

예제 입력

3
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
695

예제 출력

23
0
276

힌트