Задача C. Двойные тетради Чебурашки

Автор:C. Пак   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

У Чебурашки есть NS одинарных и ND двойных тетрадей. Все одинарные тетради имеют вес WS, а все двойные — вес WD. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

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

Формат входного файла

Во входном файле содержатся числа N M NS ND WS WD. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится Ki — число уроков в i-ый день, за которым следует Ki чисел — номера предметов. Все числа во входном файле целые.

Формат выходного файла

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

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ WS, WD ≤ 109

0 ≤ K1 + K2 + …  + KN ≤ 15

2 × ND + NS = M

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 4 0 2 2 2
2 1 2
2 3 4
2 1 2
2 3 4
8
2
4 4 2 1 0 2
2 1 2
2 3 4
2 1 2
2 3 4
4

0.072s 0.010s 13