#P3438. 小M的作物

    ID: 2637 传统题 1000ms 256MiB 尝试: 2098 已通过: 689 难度: 7 上传者: 标签>难度分类提高+/省选-图论最小割建模Dinic最大流最小割定理当前弧优化CF2200

小M的作物

小 M 的作物

题目描述

小 M 有两块容量不限的耕地 A,BA,B,以及 nn 种作物的种子,每种恰好一颗。每颗种子都要种在其中一块耕地上。作物 ii 种在 AA 可获得 aia_i 的收益,种在 BB 可获得 bib_i 的收益。

另外有 mm 个作物组合。如果第 ii 个组合中的作物全种在 AA 中,就额外获得 c1,ic_{1,i} 的收益。如果它们全种在 BB 中,就额外获得 c2,ic_{2,i} 的收益。如果分散在两块地中,该组合不产生额外收益。每个组合单独计入收益。

求可以获得的最大总收益。

输入格式

第一行包含一个整数 nn,表示作物的种数。

第二行包含 nn 个整数 a1,…,ana_1,\dots,a_n。

第三行包含 nn 个整数 b1,…,bnb_1,\dots,b_n。

第四行包含一个整数 mm,表示组合数。

接下来 mm 行。第 ii 行先给出三个整数 ki,c1,i,c2,ik_i,c_{1,i},c_{2,i},再给出 kik_i 个作物编号,表示第 ii 个组合的成员。

输出格式

输出一个整数,表示最大总收益。

样例 #1

3
4 2 1
2 3 2
1
2 3 2 1 2
11

样例解释

在 AA 种作物 1,21,2,在 BB 种作物 33。单独种植的收益为 4+2+24+2+2,作物 1,21,2 都在 AA,额外得到 33。总收益是 1111。

数据范围

1≤ki<n≤10001\le k_i<n\le 1000,1≤m≤10001\le m\le 1000。所有收益值均为 00 到 10001000 之间的整数。