Щоб підняти в свій офіс на \(N\)-му поверсі хмарочоса новий сейф, Віті знову довелося вдатися до допомоги вантажників. Але за цей час система оплати змінилася. Тепер за підйом сходами на один поверх потрібно заплатити \(U\) гривень, за спуск сходами на один поверх - \(D\) грн, за внесення до ліфта - \(I\) грн, за винесення з ліфта - \(J\) грн.

В офісі є \(L\) ліфтів, кожен із яких зупиняється лише на певних поверхах. Допоможіть Віті розробити маршрут підйому сейфа з першого поверху, вартість якого є найменшою.

Групи тестів:

• Група 0: Тести з умови (тести 1-3). 0 балів.
• Група 1: Кількість поверхів у будинку не перевищує 100 (тести 4-6). 30 балів.
• Група 2: Кількість поверхів у будинку не перевищує 1000 (тести 7-11). 30 балів.
• Група 3: \(K_1, K_2, … K_L≤1000\) (тести 12-32). 20 балів.
• Група 4: Додаткових обмежень немає (тести 33-50). 20 балів.

Бали за групу тестів виставляються лише за коректної роботи програми всіх тестах групи.

Формат вхідних даних

У першому рядку записані цілі числа \(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≤100000\).

Кількість поверхів у хмарочосі не більше 1000000.
N - не обов'язково останній поверх!

Формат вихідних даних

У вихідний потік виведіть одне число — мінімальну вартість підйому сейфа.

Приклад вхідних даних

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