Страница: 1 Отображать по:
#1087
Лифты
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Чтобы поднять в свой офис на 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
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест