Задача №1087. Лифты
Чтобы поднять в свой офис на 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≤100000. Количество этажей в небоскребе не превосходит 1000000.
В выходной файл выведите одно число — минимальную стоимость подъема сейфа.
Группы тестов:
- Группа 0 : Тесты из условия (тесты 1-3). 0 баллов.
- Группа 1 : Количество этажей в доме не превосходит 100 (тесты 4-6). 30 баллов.
- Группа 2 : Количество этажей в доме не превосходит 1000 (тесты 7-11). 30 баллов.
- Группа 3 : K1+K2+…+KL≤1000 (тесты 12-32). 20 баллов.
- Группа 4 : Дополнительных ограничений нет (тесты 33-50). 20 баллов.
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