Monk in the Magical Land

                  Monk in the Magical Land

Monk visits a magical place, Makizam. He is greeted by his old friend, Wiz. Wiz happy to see his old friend, gives him a puzzle.
He takes him to a room with N keys placed on the floor, the i'th key is of type X_i. The keys are followed by M chests of treasures, the i'th chest is of type C_i.
These chests give out gems when opened with a key. But Wiz being a clever wizard, added a spell to the chests. The spell being :
"A chest with type C_j will only open with a key of type X_i, if and if only if X_i, C_j are not co-prime. In such a case, the chest will give Z_j gems."
Wiz gives Monk the freedom to choose K keys of his choice. Monk has to find the maximum number of gems that he can have given the constraint.
Note that the gems can be obtained from a chest only once, i.e. a chest once opened, remains in the same state.

Input:
First line contains an integer T. T test cases follow.
First line of each test case contains three space seprated integers N, M and K.
Second line of each test case contains N space-separated integers, the i'th integer being X_i.
Third line of each test case contains M space-separated integers, the i'th integer being C_i.
Fourth line of each test case contains M space-separated integers, the i'th integer being Z_i.

Output:
Print the answer to each test case in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ K ≤ 10
K ≤ N ≤ 20
1 ≤ M ≤ 100
1 ≤ X_i, C_i ≤ 50
0 ≤ Z_i ≤ 1000

---

Sample Input

(Plaintext Link)

2
2 4 1 
2 3
5 3 10 2
1 2 5 7
3 4 2
2 3 5
5 3 10 2
1 2 5 7

Sample Output

(Plaintext Link)

12
14

Explanation

For the first test case, we are allowed to choose K=1 keys.
To obtain the maximum number of gems, we choose the first key with type=2. It enables us to open the Third and Fourth chest and obtain 5+7 gems.
For the second test case, we are allowed to choose K=2 keys.
To obtain the maximum number of gems, we choose the first key with type=2 (which enables Third and Fourth chest) and the second key with type=3(which enables Second chest), giving us a total of 5+7+2 gems.

******************************************editorial*****************************************

this problem can easily done using bit masking , basicically we need to bitmask keys so that we can find all possible combination of keys with no of key=k..

initially we do some precomputation . which is  ith key can open which treasure , and create a adjecency list..

now we need to just all combinations of keys with no of key =k and calculate money gain ...

***********************************************code***************************************************************

#include<iostream>
using namespace std;
typedef long long int lli;
#include<bits/stdc++.h>


 int  main()
 {
  int t;
   cin>>t;
    while(t--)
    {
    vector<int> dp[1000];
    lli ans=0;
     int n,m,k;
     
       n=read_int();
       m=read_int();
       k=read_int();
       lli maxi=pow(2,n);
       vector<pair<int,int> > v;
       int key[n+10];
       for(int i=0;i<n;i++) cin>>key[i];
       
       
        for(int i=0;i<m;i++)
        {
        int a;
        
             a=read_int();
        v.push_back(make_pair(a,0));
         
       
}
 for(int i=0;i<m;i++)
            {
            int a;
         
          a=read_int();
           v[i].second=a;
         
       
}
 
   for(int i=0;i<n;i++)
                  {
                 for(int j=0;j<m;j++)
                        {
                         int val=__gcd(key[i],v[j].first);
                         if(val!=1)
                          dp[i].push_back(j);
                          
              }
       }
       
       lli has[m+10];
       for(int i=0;i<m+1;i++) has[i]=0;
 
for(lli i=maxi;i>0;i--)
{

int bit=0;

 lli temp=0;
 
  lli var1=i;
  int ll=0;
  lli bb[100];
  int ss=0,kk=0;
  while(var1!=0)
   {
    if(var1%2==1) 
 {
  ll++;
  bb[ss]=kk;
  ss++;
 }
 kk++;
    var1/=2;
}
if(ll!=k) 
 {
  //cout<<"  contt "<<endl;
  continue;
   
 }
 
  for(int j=0;j<ss;j++)
  {
  bit=bb[j];
  vector<int> :: iterator it;
    for(it=dp[bit].begin();it!=dp[bit].end();it++)
  {
   if(has[*it]!=i )
    {
     temp+=v[*it].second;
     has[*it]=i;
     
 }
  }
}
if(temp>ans) ans=temp;
  }

  
 
        cout<<ans<<endl;
}
 }