#include<bits/stdc++.h>
using namespace std;
int a[200005],n,m,k,dep[100005],maxn;
inline int read(){
	int sum=0,x=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') x=-1;
		ch=getchar();
	} 
	while(ch>='0'&&ch<='9'){
		sum=sum*10+(ch-'0');
		ch=getchar();
	}
	return sum*x;
} 
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct node{
	int v,w,l;
};
unordered_map<int,int> dp[200005];
vector<node> g[200005];
bool check(int x,int y){
	if(x==0||y==0) return 1;
	map<int,int> mp;
	while(x>=2){
		mp[a[x]]++;
		x/=a[x];
	}
	while(y>=2){
		mp[a[y]]++;
		y/=a[y];
	}
	for(auto it:mp) if(it.second%k!=0) return 0;
	return 1;
}
void topo(){
	queue<int> q;
	for(int i=1;i<=n;i++)
		if(dep[i]==0) q.push(i);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		dp[x][0]=0;
		for(auto yy:g[x]){
			int v=yy.v,w=yy.w,l=yy.l;
			for(auto y:dp[x]){
				if(check(y.first,w))
					dp[v][w]=max(dp[v][w],y.second+l),maxn=max(maxn,dp[v][w]);
			}	
			dep[v]--;
			if(dep[v]==0) q.push(v);
		}
	}
}
signed main(){
	//freopen("P6381_16.in","r",stdin);
    for(int i=2;i<=100000;i++)
    	if(!a[i])
    		for(int j=i;j<=100000;j+=i)
    			if(!a[j]) a[j]=i;
	n=read(),m=read(),k=read();
	for(int i=1,u,v,w,l;i<=m;i++){
		u=read(),v=read(),w=read(),l=read();
		g[u].push_back({v,w,l});
		dep[v]++;
	}
	topo();
	write(maxn);
    return 0;
}

题目 记录