Share Market
Tag(s):

## Algorithms, Bitmask, Dynamic Programming, Medium-Hard

Problem
Editorial
Analytics

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$
SAMPLE INPUT
1
2
1 2
3
2 2 1
3 4 2
SAMPLE OUTPUT
Yes
No
Yes

Explanation

Here, we have one single testcase where worth of antique items are {1,2}. Now explanation regarding the purchase of 3 shares is as follow.

• Cost of first share is 3 and he wishes to buy it using 2 antique items which is possible by selling both the antique items 1 + 2 = 3 hence Yes
• Cost of second share is 4 and he wishes to buy it using 2 antique items which is not possible by selling any combination of antique items hence No
• Cost of third share is 2 and he wishes to buy it using 1 antique items which is possible by selling second antique item hence Yes
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Data Structures > Advanced Data Structures
• Data Structures > Stacks
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures