题目背景

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

题目描述

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

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

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

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

输入格式

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

第二行：包含 个整数 ，表示各板块清仓时的红利。

第三行：包含 个整数 ，表示各板块重仓时的损耗。

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

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

输出格式

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

样例

Input:

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

Output:

350

数据范围与提示

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