Автор: | C. Пак | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Пришла осень, каникулы закончились, и Чебурашке снова нужно идти в школу. Он заранее готовился к этому: накупил карандашей, ручек, тетрадей. Среди покупок, кроме обычных тетрадей, были также и двойные, каждая из которых предназначена сразу для двух предметов.
Каждый день Чебурашке нужно брать с собой тетради для всех предметов, которые будут преподаваться в его классе в этот день. Тетради тяжелые, а носить лишний вес в школу не хочется. Поэтому он пытается распределить предметы по тетрадям таким образом, чтобы за неделю переносить наименьший возможный вес. Помогите ему это сделать.
У Чебурашки есть NS одинарных и ND двойных тетрадей. Все одинарные тетради имеют вес WS, а все двойные — вес WD. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.
Требуется написать программу, вычисляющую наименьший возможный вес, который Чебурашке придется перенести в сумме за все дни недели.
Во входном файле содержатся числа NMNSNDWSWD. Далее следует расписание, состоящее из 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 |
|
|
2 |
|
|