

Advanced Speed PizzaA local pizza restaurant offers pizza delivery services to customers directly to their locations. The restaurant receives orders from multiple couriers and delivers the pizza using scooters. Orders are taken in the order provided by each courier and assigned to a driver. Each driver will have a scooter and can only pick up a single pizza order for delivery to a location. After each delivery, the driver returns to the restaurant to pick up another order, if any available, until all orders are delivered. The destination of an order can be any location on the map but will never be the restaurant's location. Locations are linked by twoway roads with an associated cost, representing the time needed for a scooter to go from one location to another. The restaurant manager wants to deliver the received orders using the available scooters while keeping the customers happy. The manager has the following information:
Of course, a customer is happy if the pizza arrives quickly. We define starvation as the time needed by a customer to receive the pizza. Therefore, the overall starvation represents the sum of starvation values for all customers from all couriers. The task of the manager is to find the value of minimum overall starvation. When assigning orders to scooters, the manager has the following rules of thumb:
Input SpecificationThe first line of the input consists of numbers l and r, representing the number of locations (numbered from 1 to l) and the number of roads that link them. On the following r lines, the twoway roads, given in the form of location l_{1}, location l_{2} and cost c, meaning that from location l_{1} to location l_{2} (and vice versa), the time to travel is c. On the following line, the location of the restaurant p is given. The next line has two numbers, representing the number of scooters s and number of couriers c. Finally, we have two lines for each courier: one with the number of orders from that courier and the following line with locations received by the restaurant from that courier, separated by a space. The order of the couriers represents the order of registration. Input Limits and Constraints
Output SpecificationIt should contain a single line representing the minimum value of overall starvation. Sample Input
Output for Sample Input
Explanation
The time to deliver pizza to locations 2, 3, 4, and 5 is 1, 3, 2, and 5. At Time 0 (both scooters are available) Scooter #1 sees orders 3 (cost 3) and order 4 (cost 2). // The manager is blind, he sees only the fist orders from the couriers and chooses the minimum cost. Scooter #1 delivers order 4 with starvation value 2. Scooter #1 will be available at time 4. // The manager is weak, he can not assign both orders, he can assign only one. After assignment he sees order 2. Scooter #2 sees orders 3 (cost 3) and 2 (cost 1). // These are now the top orders (order 4 is already assigned) of the couriers. Scooter #2 delivers order 2 with starvation value 1. Scooter #2 will be available at time 2. At Time 2 (only scooter #2 is available) Scooter #2 sees order 3 (cost 3). Scooter #2 delivers order 3 with starvation value 5. Scooter #2 will be available at time 8. At Time 4 (only scooter #1 is available) Scooter #1 sees order 5 (cost 5). Scooter #1 delivers order 5 with starvation value 9. Scooter #1 will be available at time 22. Overall starvation = 17 (2 + 1 + 5 + 9). Obs: If the manager sees more orders with the same cost, he will prefer the first one he encounters when passing through the couriers in their order of registration. Couriers are registered in the same order they are given in the input. 

University of Debrecen; Faculty of Informatics; v. 03/01/2019 