The 2004 ACM Asia Programming Contest Dhaka, sponsored by IBM

G	Travel Company
	Input	Standard Input
	Output	Standard Output

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 other 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 income 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

The first line of input is a positive integer T (T ≤ 100), the number of test cases. Then T test cases will follow. Each of the test cases will start with 3 integers. N, R, P (2 ≤ N ≤ 100, 0 ≤ R ≤ 9900, 1 ≤ P ≤ 100). N, R and P represents number of cities, number of road links and the expected profit ratio. Then R lines will follow. Each line will contain 4 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_iand E_iare the income and expenses of the road link respectively. Each test case will be followed by a blank line. 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 test case, output one line in the format “Case k: s”. Here k is the case number starting from 1 and s is a string either “YES” if there is a cyclic route for which the profit ratio is greater than P or “NO”, if there is no such route. See the sample input output for details.

Sample Input

Sample Output

3
5 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 1
3 0 11 6

5 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 2
3 0 11 6

5 8 2
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 5
3 0 11 6

Case 1: YES
Case 2: NO
Case 3: YES

Problemsetter: Md. Towhidul Islam Talukder, Special Thanks: Jane Alam Jan

Note: For the first case, consider the cycle 1 -> 4 -> 3 -> 1. Total income is 25 (5 + 11 + 9) and total expense is 8 (3 + 1 + 4). Hence the profit ratio is 25 / 8 > 3.