All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

One fine day, Monk decided to get into the share market. Being a final year student, he doesn't have a huge amount of money to invest. However, he has $$N$$ antique items each worth $$W[i]$$ units, which he is ready to sell to buy any of the $$K$$ shares to start his business. Cost of $$j^{th}$$ share is $$C[j]$$ units. Is there a way to make $$C[j]$$ units using exactly $$X[j]$$ items i.e. $$C[j]$$ = sum of worth of exactly $$X[j]$$ items.

He is really tired from all the classes and exams. Hence, he asks you to tell him if he can buy a particular share using $$X$$ items where for each share each item is only considered once and for all shares each item is available.

Input
First line of input contains $$T$$ denoting number of test cases.
Each test case begins with a single integer $$N$$ denoting the number of antique items which he is ready to sell. Next line contains $$N$$ integers separated by a space representing worth $$W[i]$$ units of each item. Next line contains an integer $$K$$ denoting the number of shares Next line contains an array of $$K$$ integers representing $$X$$, each integer represents $$X[i]$$. Last line contains an array of $$K$$ integers representing cost of each share $$C[i]$$.

Output
For each testcase, print $$K$$ lines. Each line of the test-case represents if it possible to buy a share $$i$$ having cost $$C[i]$$ units using exactly $$X[i]$$ items. Print "Yes" if it is possible, "No" otherwise.

Constraints

• $$1 ≤ T ≤ 1000$$
• $$1 ≤ N ≤ 50$$
• $$1 ≤ W[i] ≤ 100$$
• $$1 ≤ K ≤ 500$$
• $$1 ≤ X[i] ≤ 50$$
• $$1 ≤ C[i] ≤ 5000$$