- Купоны на скидку
Семен очень любит скидки. Но в онлайн магазине их не так просто применить. Дело в том, что некоторые виды скидок применимы только к части товаров. Кроме этого в магазине к корзине товаров можно применить не более k скидочных купонов.
Даны список из m скидочных купонов, которые получил Семен, и список из n товаров в корзине. Определите, какие купоны следует применить Семену, чтобы купить все товары из корзины с наибольшей скидкой. В этот раз Семен не будет разделять товары на разные покупки, но собирается подумать об этом в будущем.
Про каждый купон известна величина скидки discounti, а про каждый товар известен список номеров купонов, которые к нему применимы.
Обратите внимание, что очередной купон применяется к текущей стоимости товара: если товар сначала стал дешевле на 10%, а затем еще на 20%, то итоговая его стоимость на 28% меньше начальной, а не на 30%.
Также стоит заметить, что итоговая стоимость корзины товаров зависит от множества примененных купонов, но не зависит от порядка их применения. Это утверждение будем считать дополнительным упражнением для решающего эту задачу.
Формат ввода
В первой строке записаны три целых числа n, m и k (1≤n≤100, 1≤m≤20, 1≤k≤min(6,m)) - количество товаров, количество купонов и максимальное количество применимых купонов.
Вторая строка содержит nn целых числе cost1, ……, costn (1≤costi≤104) - стоимость товаров для применения скидок.
В следующих n строках идут описания применимых скидок к товарам.
В i-й строке сначала записано число ci (0≤ci≤m) - количество купонов, которые влияют на стоимость i-го товара. Далее следуют ci различных целых чисел aij (1≤aij≤m) - номера купонов.
В последней строке записано m чисел discount1, ……, discountm (1≤discounti≤99) - значения скидок для всех купонов.
Формат вывода
В первой строке выведите количество примененных купонов t (0≤t≤k).
Во второй строке выведите t различных целых чисел ui (1≤ui≤m) - номера выбранных купонов.
Если оптимальных решений несколько, то выведите любое из них.