|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||||||||
|
I Всероссийская заочная олимпиада школьников по информатике, 2006/07 учебный год
Задача E. Лифты
| Имя входного файла: | e.in |
| Имя выходного файла: | e.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж - D рублей, за внос в лифт - I рублей, за вынос из лифта - J рублей.
В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.
Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.
Формат входных данных
В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki - количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел - этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+...+KL≤1000. Количество этажей в небоскребе не превосходит 1000000.
Формат выходных данных
В выходной файл выведите одно число - минимальную стоимость подъема сейфа.
Примеры
| e.in | e.out |
10 1 1 1 1 1 2 3 7 |
7 |
10 1 1 3 2 1 2 3 7 |
9 |
20 100 0 1 1 2 2 5 7 2 8 17 |
804 |