#P3438. 小M的作物
小M的作物
小 M 的作物
题目描述
小 M 有两块容量不限的耕地 ,以及 种作物的种子,每种恰好一颗。每颗种子都要种在其中一块耕地上。作物 种在 可获得 的收益,种在 可获得 的收益。
另外有 个作物组合。如果第 个组合中的作物全种在 中,就额外获得 的收益。如果它们全种在 中,就额外获得 的收益。如果分散在两块地中,该组合不产生额外收益。每个组合单独计入收益。
求可以获得的最大总收益。
输入格式
第一行包含一个整数 ,表示作物的种数。
第二行包含 个整数 。
第三行包含 个整数 。
第四行包含一个整数 ,表示组合数。
接下来 行。第 行先给出三个整数 ,再给出 个作物编号,表示第 个组合的成员。
输出格式
输出一个整数,表示最大总收益。
样例 #1
3
4 2 1
2 3 2
1
2 3 2 1 2
11
样例解释
在 种作物 ,在 种作物 。单独种植的收益为 ,作物 都在 ,额外得到 。总收益是 。
数据范围
,。所有收益值均为 到 之间的整数。