Elevators#2209
To transport a new safe to his office on the -th floor of a skyscraper, Vitya again needs the assistance of movers. However, the payment system has now changed. Moving up one floor by stairs costs units, moving down one floor by stairs costs units, entering an elevator costs units, and exiting an elevator costs units.
There are elevators in the building, each stopping only at specific floors.
Help Vitya plan the least expensive route to move the safe from the first floor to his office.
The first line contains integers , , , , , .
Each of the next lines describes an elevator. Each line starts with K_i — the number of floors where the -th elevator stops, followed by K_i natural numbers — the floors where this elevator stops (for each elevator, the floors are listed in ascending order).
0 \leq U \leq 1000, 0 \leq D \leq 1000, 0 \leq I \leq 1000, 0 \leq J \leq 1000, 0 \leq L \leq 500, 1 \leq N \leq 1000000, 2 \leq K_i \leq 1000, K_1 + K_2 + \dots + K_L \leq 1000.
The total number of floors in the skyscraper does not exceed .
Output a single number — the minimal cost of lifting the safe.
Primer 1