eolymp
bolt
Try our new interface for solving problems
Məsələlər

Лифты

Лифты

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.

В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.

Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.

Giriş verilənləri

В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа K_i — количества этажей, на которых останавливается i-й лифт, за которым следует K_i натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0U1000, 0D1000, 0I1000, 0J1000, 0L500, 1N1000000, 2K_i1000, K_1+K_2+…+K_L1000. Количество этажей в небоскребе не превосходит 1000000.

Çıxış verilənləri

В выходной файл выведите одно число — минимальную стоимость подъема сейфа.

Nümunə

Giriş verilənləri #1
10 1 1 1 1 1
2 3 7
Çıxış verilənləri #1
7