Little Min’s family has a grocery store，and she helps her parents to weight the goods everyday. She often wants to know whether the quality of the goods they sell can be equal to the sum quality of several poise weights. Suppose there are N kinds of poise weights, but there are M pairs of them can’t be used at the same time, and we know the quality of the goods is V. The question is: can little Min exactly take K form N poise weights, and their sum quality is equal to the goods’ quality?

The first line contains an integer T, the number of test cases (T < 25). Each test case is in the following format.The first line starts with four integers N (1 <= N <= 32) denoting the number ofpoise weights and M (0 <= M <= 6),K(1<=K<=N),V(1<=V<=1000000000). The second line has N integer ai each denoting the kind poise weight's quality(1<=i<=N,1<=ai<=1000000000).Then following M lines, each line has two integers a and b, which denoting the a-th poise weight can't be used with the b-th poise weight at the same time(1<=a,b<=N,a!=b).

For each test case, print one line containing YES if there exist exactly K poise weights' sum quality is equal to the good's quality, or output NO.

2
5 1 3 1000
100 200 300 500 600
2 3
5 2 3 1000
100 200 300 500 600
2 3
1 5

YES
NO

HDU 3rd “Vegetable-Birds Cup” Programming Open Contest