It’s year 2258, and the age of airplanes is coming to an end. Everyone is using teleporters now. In an effort to stay competitive, the last remaining air travel company, GetsJo, is offering the following deal to its customers. Instead of buying one plane ticket, you can rent a whole flight from A to B. Each flight can carry a certain number of people and costs a certain amount of money. If you do that, then you can rent all of the other flights of equal or lesser cost for free! For example, if there are 4 flights with costs $10000, $25000, $30000 and $40000, and you rent the $30000 flight, then you get the $10000 and $25000 flights for free. The total cost to rent these 3 flights is $30000. You want to organize a large programming competition and would like to invite all of the participants to city n, where the competition will be held. Being a nice person, you decide to pay for everyone’s airplane tickets. Given the locations of the participants and the list of available flights between now and the day of the competition, what is the cost of renting enough flights to get all of the participants to city n in the next d days? Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing the number of cities (1 ≤ n ≤ 30), the number of days (1 ≤ d ≤ 10) until the competition and the number of flights (0 ≤ m ≤ 1000). m lines follow, each one containing 5 integers: u, v, c, p ande(1≤u,v≤n,1≤c≤100,0≤e<d). Thismeansthataflightthatcancarrycpassengersand costs p dollars leaves city u on day e in the evening and arrives next day in the morning to city v. Day 0 is today, and all of the participants need to be in city n in the evening of day e. Finally, n integers (z1,z2,...,zn) follow, meaning that there are zi participants in city i on day 0 (0 ≤ zi ≤ 100). The maximum cost of a flight is 100000. There will never be two flights with the same u, v and e values. Output For each test case, output one line containing ‘Case #x:’ followed by the minimum required cost of flying all of the participants to city n before the end of day d. If no amount of money is enough, print ‘Impossible’ instead. Sample Input 2 545 1 5 100 30000 0 2 4 10 10000 0 2 4 10 10000 1 4 5 25 25000 2 2 5 100 40000 3 1 20 0 5 100 211 1 2 99 10400 0 100 0 “Whoa! It feels like I’m flying!” Lrrr
2/2 Sample Output Case #1: 30000 Case #2: Impossible