#P1361. 小M的作物
小M的作物
题目描述
小 M 在 MC 里开辟了两块巨大的耕地 和 (你可以认为容量是无穷),现在,小 P 有 种作物的种子,每种作物的种子有 个(就是可以种一棵作物),编号为 到 。
现在,第 种作物种植在 中种植可以获得 的收益,在 中种植可以获得 的收益,而且,现在还有这么一种神奇的现象,就是某些作物共同种在一块耕地中可以获得额外的收益,小 M 找到了规则中共有 种作物组合,第 个组合中的作物共同种在 中可以获得 的额外收益,共同种在 中可以获得 的额外收益。
小 M 很快的算出了种植的最大收益,但是他想要考考你,你能回答他这个问题么?
输入格式
第一行一个整数 ,表示作物种数。
第二行 个整数,表示 。
第三行 个整数,表示 。
第四行一个整数 ,表示组合种数。
接下来 行中,第 行第一个整数 ,表示第 个作物组合中的作物种数,接下来两个整数 ,然后 个整数,表示该组合中的作物编号。
输出格式
只有一行,包括一个整数,表示最大收益。
3
4 2 1
2 3 2
1
2 3 2 1 2
11
提示
样例解释
耕地种作物 , 耕地种作物 ,收益: 。
数据范围
对于 的数据,,。