数据不是很大，直接枚举约数，判断4个条件是否满足！
这样就得到4种卡片，总共2^4种情况，枚举各种情况即可！！！
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAX 5000005
#define ll long long
using namespace std;
bool ispri[MAX];
int extra[];
struct card
{
int score,num,s;
}p[];
bool cmp(const card &aa,const card &bb){
return aa.score>bb.score?:;
}
void init(){
ll i,j;
ispri[]=;
for (i=;i<MAX;i++){
if (ispri[i]==){
for (j=i*i;j<MAX;j+=i)
ispri[j] = ;
}
}
}
void factor(int n,int k){
ll i,j,num=,sum=,mul=,t;
for (i=;i*i<=n;i++){
if (n%i==){
num ++;
sum += i;
mul = (ll)mul*i;
if (i*i != n){
num ++;
sum += n/i;
mul = (ll)mul*(n/i);
}
if (mul == (ll)n*n)
mul = ;
}
}
p[k].s = ;j = ;
if (ispri[n]==){
p[k].s |= (<<);
j ++;
}
if (ispri[num]==){
p[k].s |= (<<);
j ++;
}
if (ispri[sum]==){
p[k].s |= (<<);
j ++;
}
t = (ll)sqrt(mul+0.0);
if (t*t==mul||(t+)*(t+)==mul||(t-)*(t-)==mul){
p[k].s |= (<<);
j++;
}
p[k].score = j;
}
int main(){
init();
int t,i,j,k,n,aa;
cin>>t;
while (t--){
cin>>n>>k;
for (i=;i<n;i++){
cin>>aa>>p[i].num;
if (aa==){
p[i].score = ;
p[i].s = (<<);
}
else factor(aa,i);
}
for (i=;i<;i++){
cin>>extra[i];
}
cout<<p[].score;
for (i=;i<n;i++){
cout<<' '<<p[i].score;
}
cout<<endl;
sort(p,p+n,cmp);
ll ans = -(<<);
for (i=;i<(<<);i++){
ll temp=,an=k,flag=;
for (j=;j<n;j++){
if ((i&p[j].s)==){
if (p[j].num < an){
temp += p[j].score*p[j].num;
an -= p[j].num;
flag |= p[j].s;
}
else{
temp += p[j].score*an;
an = ;
flag |= p[j].s;
break;
}
}
}
for (j=;j<;j++){
if ((flag&(<<j))==)
temp += extra[j];
}
if (an != ) continue;
else ans = max(ans,temp);
}
cout<<ans<<endl;
}
return ;
}