You are the King of Byteland, and your most important responsibility is management of resources of the kingdom.
Byteland has
N cities numbered from 0 to
N-1 and an infinite number of people. You must assign some number of people to each city (at least 1 , and at most
M to each city). If a person lives in city
i, his monthly savings are
S[i] rupees. (Savings can be negative too, if the city is an expensive place to live in).
Some cities can be made "special cities". Special cities are alloted special funds. If ith city is a special city, it gets an amount of
F[i] rupees as fund. However , special cities also require extra maintainence, hence require
C[i] rupees as maintainence costs.
Also, there are
K relationships between cities:
x y denotes that city
y must contain at least as many residents as city
x.
Find wether there exists a distribution of people as well as a selection of special cities such that the per-capita profits of the kingdom exceeds the net costs, i.e. if number of residents of city
i is
count[i]:
Input:
First line contains
T, the number of test cases.
First line of each test case contains 3 numbers:
N,
M and
K
The next line contains
n numbers:
ith number is
S[i-1]
The next line contains
n numbers:
ith number is
F[i-1]
The next line contains
n numbers:
ith number is
C[i-1]
The next
K lines contain 2 integers each:
x y denoting that city
y should have at least as many residents as city
x
Output:
Output
YES if it is possible to find such a distribution of people as well as a selection of special cities. Output
NO otherwise
Constraints:
1<=T,N,M<=50
-10^9 <= S[i] <= 10^9
0<= F[i],C[i]<=10^9
0 <= x !=y < N
Sample Input:
1
3 2 2
-10 5 20
10 10 10
5 5 5
1 2
2 3
Sample Output:
YES
Explanation:
Count[] = [1,1,2]
Make only city 2 (0-based indexing) special.
LHS: (-10+5+40+10)/4 = 45/4
RHS: 5
