Server Time: Mon Aug 20, 2018 1:28 am
Welcome ( logout
1221 - Travel Company
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

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 P represents number of cities, number of road links and the expected profit ratio respectively. Then R lines follow. Each line contains four integers Ai, Bi, Ii, Ei (0 ≤ Ai, Bi < N, 0 ≤ Ii ≤ 5000, 1 ≤ Ei ≤ 5000). (Ai, Bi) represents directed road link from city Ai to Bi. Ii and Ei are the incomes and expenses of the road link respectively. You may assume that (Ai, Bi) ≠ (Aj, Bj), if i ≠ j and Ai ≠ Bi 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.

Sample Input

Output for Sample Input

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

Note

Dataset is huge. Use faster I/O methods.


Problem Setter: Md. Towhidul Islam Talukder
Special Thanks: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan