Подразделы

Другие разделы

Дата и время

09/04/2025 15:18:40

Авторизация

Лето 10

A. Куб со спицами B. Мосты-горки C. Марсианская оптимизация D. Замена скобок: минимизация шагов E. Марсианские суеверия F. Двойные тетради Чебурашки G. Замена скобок: выполнение алгоритма H. Шушанчики и кроссворд I. Frogless swamp

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

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

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

У Чебурашки есть

$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$

Пример ввода 1

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

Пример вывода 1

Пример ввода 2

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

Пример вывода 2

Источник: C. Пак, ДВГУ, Весенний турнир, 2007