Лифты
Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.
В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.
Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.
Входные данные
В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа K_i — количества этажей, на которых останавливается i-й лифт, за которым следует K_i натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0 ≤ U ≤ 1000, 0 ≤ D ≤ 1000, 0 ≤ I ≤ 1000, 0 ≤ J ≤ 1000, 0 ≤ L ≤ 500, 1 ≤ N ≤ 1000000, 2 ≤ K_i ≤ 1000, K_1+K_2+…+K_L ≤ 1000. Количество этажей в небоскребе не превосходит 1000000.
Выходные данные
В выходной файл выведите одно число — минимальную стоимость подъема сейфа.