Peoples of TomatoLand are fond of tomato sauce. The only company that makes tomato sauce is Crushtomato which is in city N. Maketomato is a tomato supplier company which is in City 1. After trying for one year, Maketomato finally made a deal with Crushtomato that they will supply tomato as much as possible for next K days. If any tomatoes reach Crushtomato after Kth day, then Crushtomato will not receive them. Maketomato will use truck to supply tomatoes and each truck can carry at most 100 tomatoes.
The country TomatoLand has N cities and M bidirectional roads. For each road i, a truck takes Di days to reach city Vi from city Ui and vice versa. If a truck starts its journey from city Ui at day X using road i, then it will reach city Vi at day (X+Di). Due to traffic policies, on each day at most Ci trucks can start their journey from each endpoint of the ith road.
Crushtomato company has some holidays. If a truck arrives at Crushtomato company in one of these holidays, the Crushtomato company cannot store them. So they will rot due to weather of city N and Crushtomato will not pay for them.
Now, Maketomato company wants to know maximum how many tomatoes they can supply to Crushtomato company in next K days (starting from day 1) without wasting any tomatoes. For your information, they have unlimited number of trucks.
Input
Input starts with an integer, T (T ≤ 30) denoting the number of test cases. Each test case starts with four integers, N (2 ≤ N ≤ 50), M (1 ≤ M ≤ N ∗ (N-1)/2), K (1 ≤ K ≤ 100) and H (0 ≤ H ≤ K-1). Each of the next M lines contain four integers Ui , Vi , Di and Ci (1 ≤ Ui , Vi ≤ N, Ui ≠ Vi , 1 ≤ Di , Ci ≤ 100), description of the road i. The Last line of each test contains H integers which represent the holidays of Crushtomato (1 ≤ Hi ≤ K). There will always be at least one path from City 1 to City N and at most one road between two cities.
Output
For each case, print the maximum number of tomatoes that can be sent in K days followed by the case number. See I/O for clarification.
Sample
| Input | Output |
|---|---|
2 2 1 3 1 1 2 1 2 3 4 4 15 2 1 2 3 2 1 3 1 2 2 4 2 1 3 4 2 1 9 13 | Case 1: 200 Case 2: 1800 |
Explanation of case 1:
Day 1: 2 trucks start their journey from city 1 using road 1
Day 2: 2 trucks reach city 2 using road 1
Maketomato will not send any truck after day 1 from city 1 because they will reach the city 2 after day 2 and day 3 is the holiday for Crushtomato.
