//rohitaas_15
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
void co(auto x) {cout<<x<<"\n";}
void co(auto a,auto b) {cout<<a<<" "<<b<<"\n";}
void co(auto a,auto b,auto c) {cout<<a<<" "<<b<<" "<<c<<"\n";}
void co(auto a,auto b,auto c,auto d){cout<<a<<" "<<b<<" "<<c<<" "<<d<<"\n";}
#define ld long double
#define ll long long
#define int ll
#define dd double
#define rohitaas_15(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(),v.end()
#define f(a,b) for(int i=a;i<=b;i++)
#define f2(a,b) for(int j=a;j<=b;j++)
#define f3(a,b) for(int kk=a;kk<=b;kk++)
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define ff first
#define ss second
#define nl cout<<"\n"
#define lb(v,x) lower_bound(v.begin(),v.end(),x)
#define ub(v,x) upper_bound(v.begin(),v.end(),x)
#define pv(v,x,n) if(n!=0){f(x,n-1){cout<<v[i]<<" ";}cout<<endl;}
#define cn(v,x,n) f(x,n){cin>>v[i];}
#define check() cout<<"hi"<<"\n"
#define M1 1000000007
#define M2 998244353
#define con continue
#define maxv(v) *max_element(all(v));
#define minv(v) *min_element(all(v));
#define sumv(v) accumulate(all(v),0ll)
#define pf push_front
#define popb pop_back
#define popf pop_front
#define br break
#define rev(x) reverse(all(x))
#define vr vector<ll>
#define vvr vector<vr>
#define vll vector<pii>
#define PI 3.141592653
#define MLL map<ll,ll>
#define yes co("YES");
#define no co("NO");
#define fbo find_by_order
#define ook order_of_key
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define debug1(a) cout<<#a<<" = "<<(a)<<endl;
#define debug2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl
#define debug3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl
#define debug4(a,b,c,d) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<", "<<#d<<" = "<<(d)<<endl
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll gcd(ll a, ll b) {if(!b)return a;return gcd(b, a % b);}
ll lcm(ll a , ll b) {return (a*b)/ gcd(a,b);}
ll modmul(ll a, ll b,ll mod) { return ((a%mod) * (b%mod)) % mod;}
ll modadd(ll a , ll b,ll mod) { return((a%mod)+(b%mod)+mod)%mod;}
ll modsub(ll a , ll b,ll mod) {return((a%mod) - (b%mod) + mod)%mod;}
ll moduloMul(ll a,ll b,ll mod) {ll res = 0;a %= mod;while (b){if (b & 1)res = (res + a) % mod;a = (2 * a) % mod;b >>= 1;}return res;}
/*ll power(ll x,ll y,ll p=LLONG_MAX) {ll res = 1;x = x % p;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}ll XFEEA,YFEEA,GCDFEEA;
double power2(double x, ll y) {double res = 1;while (y > 0){if (y & 1)res =(double) (res*x);y = y>>1;x =(double)(x*x);}return res;}
void extendedEuclidAlgo(ll a,ll b) {if(b==0){XFEEA=1;YFEEA=0;GCDFEEA=a;return;}extendedEuclidAlgo(b,a%b);ll cx=YFEEA;ll cy=XFEEA-(a/b)*YFEEA;YFEEA=cy;XFEEA=cx;}
ll modInverse(ll n,ll m) {extendedEuclidAlgo(n,m);return (XFEEA%m+m)%m;}
ll CmP(ll n, ll r, ll p=M1) {if (r==0)return 1;ll fac[n+1];fac[0] = 1;for (ll i=1 ; i<=n; i++)fac[i] = fac[i-1]*i%p;return (fac[n]* modInverse(fac[r], p) % p *modInverse(fac[n-r], p) % p) % p;}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> orderedset;*/
/*find_by_order(ll k){returns the iterator to the kth smallest element,start from 0,O(logn)}
order_of_key(ll k){returns the number of elements in the set which are strictly less than our k,O(logn)}*/
int numberOfTringles(vr count, ll k)
{
int sum1 = 0;
for (int i=0; i<k; i++)
sum1 += count[i];
int sum2 = 0;
int temp[k+1];
for (int i=0; i<k; i++)
{
temp[i] = count[i]*(sum1-count[i]);
sum2 += temp[i];
}
sum2 /= 2;
int sum3 = 0;
for (int i=0; i<k; i++)
sum3 += count[i]*(sum2-temp[i]);
sum3 /= 3;
return sum3;
}
pii fun(vr count)
{
int sum1 = 0;
for(auto i : count)
{
if(i>0)
{
sum1 +=(ll)i;
}
}
int sum2 = 0;
ll minn=LLONG_MAX;
ll index=-1;
ll len=count.size();
f(0,len-1)
{
if(count[i]<=0)
{
con;
}
ll x= count[i]*(sum1-count[i]);
sum2 +=x;
if(x<=minn)
{
minn=x;
index=i;
}
}
if(sum2%2!=0)
{
return mp(0,-1);
}
sum2 /= 2;
if(sum2==0)
{
return mp(0,-1);
}
return mp(sum2-minn,index);
}
int UK(int W, int c, vr coc,vvr &removal,ll ini)
{
vr dp(W+1,0ll);
vvr counts(W+1,vr(c+1,0ll));
for (int i=0; i<=W; i++)
{
ll color=-1;
if(i!=0)
dp[i]=dp[i-1];
for (int j=1; j<=c; j++)
{
if (coc[j] <= i)
{
ll len=removal[j].size();
if(counts[i-coc[j]][j]+1>=len)
{
con;
}
if(dp[i-coc[j]]+removal[j][counts[i-coc[j]][j]+1]>dp[i])
{
dp[i]=dp[i-coc[j]]+removal[j][counts[i-coc[j]][j]+1];
color=j;
}
}
}
if(color!= -1)
{
counts[i]=counts[i-coc[color]];
counts[i][color]++;
}
else
{
if(i!=0)
{
dp[i]=dp[i-1];
counts[i]=counts[i-1];
}
}
}
ll ans=-1;
for(auto i : dp)
{
ans=max(ans,i);
}
return min(ans,ini);
}
void solve(){}
void ask(){}
signed main()
{
//rohitaas_15();
ll t=1;
cin>>t;
ll cccc=t;
while(t--)
{
ll n,c,k;
cin>>n>>c>>k;
map<ll,map<ll,ll> > cfreq;
f(1,n)
{
ll x,y,z;
cin>>x>>y>>z;
cfreq[z][x]++;
}
vr coc(c+1);
cn(coc,1,c);
vector<vr> slfreq(c+1);
for(auto i : cfreq)
{
for(auto k : i.ss)
{
slfreq[i.ff].pb(k.ss);
}
}
ll ini=0;
f(1,c)
{
if(coc[i]==0)
{
con;
}
if(slfreq[i].size()<=2)
{
con;
}
vector<ll> temp;
for(auto k : slfreq[i])
{
temp.pb(k);
}
ini+=numberOfTringles(temp,slfreq[i].size());
}
if(k==0 || ini==0)
{
co(ini);
con;
}
vector<vr> removal(c+1);
f(1,c)
{
removal[i].pb(0);
if(coc[i]==0)
{
con;
}
ll cnt=1;
while(true)
{
vector<ll> temp;
ll flag=0;
for(auto kk : slfreq[i])
{
if(kk>0)
{
flag=1;
}
temp.pb(kk);
}
if(!flag)
{
break;
}
pii x=fun(temp);
if(x.ff==0)
{
br;
}
removal[i].pb(x.ff);
slfreq[i][x.ss]--;
cnt++;
}
}
ll rem=UK(k,c,coc,removal,ini);
co((ini-rem));
}
printclock;
}
/*cout<<"Case #"<<cccc-t<<": ";*/