Лето 10

Пришла осень, каникулы закончились, и Чебурашке снова нужно идти в школу. Он заранее готовился к этому: накупил карандашей, ручек, тетрадей. Среди покупок, кроме обычных тетрадей, были также и двойные, каждая из которых предназначена сразу для двух предметов.

Каждый день Чебурашке нужно брать с собой тетради для всех предметов, которые будут преподаваться в его классе в этот день. Тетради тяжелые, а носить лишний вес в школу не хочется. Поэтому он пытается распределить предметы по тетрадям таким образом, чтобы за неделю переносить наименьший возможный вес. Помогите ему это сделать.

У Чебурашки есть `N_S` одинарных и `N_D` двойных тетрадей. Все одинарные тетради имеют вес `W_S`, а все двойные – вес `W_D`. Чебурашка учится `N` дней в неделю. Он изучает `M` предметов, пронумерованных от `1` от `M`. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

Требуется написать программу, вычисляющую наименьший возможный вес, который Чебурашке придется перенести в сумме за все дни недели.

Во входном файле содержатся числа `N,\ M,\ N_S,\ N_D,\ W_S,\ W_D`. Далее следует расписание, состоящее из `N` дней. Каждый день описывается одной строкой. В начале строки содержится `K_i` – число уроков в `i`-ый день, за которым следует `K_i` чисел – номера предметов. Все числа во входном файле целые.

В выходном файле должно содержаться единственное число – минимальный возможный вес.

`0\ ≤\ N\ ≤\ 6`, `0\ ≤\ M\ ≤\ 10`, `0\ ≤\ W_S,\ W_D\ ≤\ 10^9`, `0\ ≤\ K_1\ +\ K_2\ +\ …\ +\ K_N\ ≤\ 15`, `2\ *\ N_D\ +\ N_S\ =\ M`

4 4 0 2 2 2
2 1 2
2 3 4
2 1 2
2 3 4

8

4 4 2 1 0 2
2 1 2
2 3 4
2 1 2
2 3 4

4