A travel company is planning to launch their bus service in a new route. So they conducted a survey and made a list of all possible roads connecting different cities. Each of the roads has a certain amount of income based on current fare. But at the same time, each road has some expenses too (this includes fuel and maintenance cost, staff payments, taxes and tribute to labor union which is recently approved by the Government). The travel company is looking for a cyclic route. That is, the bus will start from any city, then visit one or more cities each exactly once and return to the starting city. The company is also concerned with the profit on the route. In fact the directors of the company have a strict requirement of a profit ratio strictly greater than P. Otherwise they will not launch the service. A profit ratio for a route is the ratio between the total incomes to the total expenses for that route.

One of your friends works in that company and he asks for a little help from you. All you have to do is to determine if there exists such route, so that the company has a profit ratio of P.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line and three integers N, R, P (2 ≤ N ≤ 100, 0 ≤ R ≤ 9900, 1 ≤ P ≤ 100). N, R and Prepresents number of cities, number of road links and the expected profit ratio respectively. Then R lines follow. Each line contains four integers A_i, B_i, I_i, E_i (0 ≤ A_i, B_i < N, 0 ≤ I_i ≤ 5000, 1 ≤ E_i ≤ 5000). (A_i, B_i) represents directed road link from city A_i to B_i. I_i and E_i are the incomes and expenses of the road link respectively. You may assume that (A_i, B_i) ≠ (A_j, B_j), if i ≠ j and A_i ≠ B_i for any i.

Output

For each case, print the case number and "YES" if there is a cyclic route for which the profit ratio is greater than P or "NO", if there is no such route.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <list>
using namespace std;
const  int maxn=50100;
const int INF=0x3f3f3f3f;
int n,m,dis[maxn],vis[maxn],intime[maxn];
vector < pair<int,int> > eg[maxn];
int spfa(int src)
{
	queue <int> Q;
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(intime,0,sizeof(intime));
	dis[src]=0;
	Q.push(src);
	while(!Q.empty())
	{
      int u=Q.front();Q.pop();
      vis[u]=0;intime[u]++;
      if(intime[u]>n)
		return 1;
	  int len=eg[u].size();
	  for(int i=0;i<len;i++)
	  {
	  	int v=eg[u][i].first;
	  	int w=eg[u][i].second;
	  	if(dis[v]>dis[u]+w)
		{
			dis[v]=dis[u]+w;
			if(!vis[v])
			{
				vis[v]=1;
				Q.push(v);
			}
		}
	  }
	}
	return 0;
}
int main()
{
    int T,p,cas=1;
    scanf("%d",&T);
    while(T--){
		scanf("%d%d%d",&n,&m,&p);
		for(int i=0;i<=n;i++)
			eg[i].clear();
		while(m--)
		{
			int u,v,in,out;
			scanf("%d%d%d%d",&u,&v,&in,&out);
			int tem=out*p-in;
			eg[u].push_back(make_pair(v,tem));
		}
		printf("Case %d: ",cas++);
		int flag=1;
		for(int i=0;i<n;i++)
		{
			if(spfa(i))
			{
				flag=0;
				printf("YES\n");
				break;
			}
		}
		if(flag)
			printf("NO\n");
    }
	return 0;
}