Advanced Speed Pizza

A 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 two-way 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:

• a map of locations numbered from 1 to l, linked by two-way roads with a time cost;
• the location of the restaurant;
• the total number of available scooters;
• the number of couriers;
• for each courier, we know the number of orders and their location.

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:

1. The manager is greedy! The manager will always assign the order with minimum cost.
2. The manager is blind! At each moment, he assigns only from orders that he sees, and he sees only the first order from each courier.
3. The manager is weak! At each moment, he can choose only one order and assign it to a scooter, although there could be two available scooters at the same time.
4. The manager has a preference over couriers! The order in which the couriers have been registered to the restaurant represents the preference order of the manager. Suppose two (or more) orders from distinct couriers have the same cost (i.e., delivery time). In this case, the manager will always prefer the order from the courier who registered earlier to the restaurant.

Input Specification

The 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 two-way roads, given in the form of location l₁, location l₂ and cost c, meaning that from location l₁ to location l₂ (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

• 1 < l < 100 000
• 1 < r < 150 000
• 1 < s ≤ c < 100 000
• The locations are reachable from the restaurant.
• The overall starvation will fit in 64 bit.
• There is no limitation on the number of scooters on the road at any moment in time.
• The sum of overall orders from all couriers will be less than 100 000.

Output Specification

It should contain a single line representing the minimum value of overall starvation.

Sample Input

1. 5 6
2. 1 2 1
3. 1 4 2
4. 4 3 4
5. 2 3 2
6. 4 5 3
7. 3 5 6
8. 1
9. 2 2
10. 2
11. 3 5
12. 2
13. 4 2

download as text file

Output for Sample Input

1. 17

download as text file

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.