You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

题目背景

作为华尔街天才操盘手，你研发了一套高频交易协议。该协议在接下来 $k$ 个交易期内，会在金融市场上自动套利。

题目描述

现在市场上会有 $n$ 个板块，在任意一个交易期中你的基金对每个板块只有两种持仓状态：“重仓” 或 “空仓”。 初始时，所有板块状态均为重仓。 你需要在接下来的 $K$ 个交易期内，每期从 $m$ 种可选策略中选择且仅选择一种执行。每一种策略对各板块的影响如下：

• 强制买入：将板块状态变成重仓（若已是重仓则维持不变）。
• 强制卖出：将板块状态变成空仓（若已是空仓则维持不变）。
• 维持现状：该板块保持上一期的状态不变。 保证同一个策略中，要求强制清仓和强制重仓的板块编号互不重复

每一期的策略执行之后，若板块 $i$ 发生变化，将产生如下收益：

1. 清仓收入：板块状态由重仓变成空仓，获得 $A_i$ 元。
2. 建仓支出：板块状态由空仓变成重仓，支付 $D_i$ 元。
3. 无变化：状态保持不变，收益为 0。 你需要指定一份 $k$ 期的策略顺序，使得在期末的累计收益最大。

输入格式

第一行：包含三个正整数 $n,m,k$ 分别表示板块总数、可选策略数以及总交易期数。

第二行：包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示各板块清仓时的红利。

第三行：包含 $n$ 个整数 $D_1, D_2, \dots, D_n$，表示各板块重仓时的损耗。

接下来 $2m$ 行：每两行为一个策略描述。对于第 $j$ 个策略：

• 第一行：首先输入一个非负整数 $x_j$，表示该策略强制清仓的板块数量；紧接着输入 $x_j$ 个不同的整数，表示对应板块的编号（范围为 $1 \dots n$）。
• 第二行：首先输入一个非负整数 $y_j$，表示该策略强制重仓的板块数量；紧接着输入 $y_j$ 个不同的整数，表示对应板块的编号（范围为 $1 \dots n$）。 保证同一个策略中，要求强制清仓和强制重仓的板块编号互不重复

输出格式

输出一个整数，表示可能获得的最大净总收益。

样例

Input:

2 2 3
100 200
50 60
1 1
0
1 2
1 1

Output:

350

数据范围与提示

$1 \le n \le 7,1 \le m \le 100$

$1 \le k \le 1e9$

$1 \le A_i,D_i \le 1e5$

提示：投资有风险，炒股需谨慎

Output Format

Sample