Олимпиады по программированию

olympiads.ru

Олимпиады прошлых лет
2020/21
2019/20
2018/19
2017/18
2016/17
2015/16
2014/15
2013/14
2012/13
2011/12
2010/11
2009/10
2008/09
2007/08
2006/07

I Всероссийская заочная олимпиада школьников по информатике (2006/07)
Документы
Информация об олимпиаде
Обращение к организаторам региональных олимпиад
Регионы, участвующие в олимпиаде
Задачи и результаты
Задачи
Тесты и решения
Персональная страничка участника
Предварительные результаты
Результаты проверки решений на похожесть
Окончательные результаты
Дипломы
Статистика
Дополнительная информация
FAQ по работе с тестирующей системой
Несколько советов участникам олимпиад
Связаться с оргкомитетом

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