研学名额

题目背景

学校要从若干名同学里选出一批参加研学活动。每名同学需要交纳一笔报名费，同时会给活动带来一份“收获值”。活动的经费有限，但学校希望这批同学带来的总收获值尽可能大。

负责报名的老师还提了一个要求：有些同学是两两组队报名的，老师希望同一小组的同学要么一起被选上，要么一起落选，不能只选其中一个人。

题目描述

共有 $n$ 名同学报名，第 $i$ 名同学的报名费为 $c_i$ 元，能带来的收获值为 $v_i$。

这 $n$ 名同学被划分成 $m$ 个小组，每个小组包含 $1$ 名或 $2$ 名同学，每个同学恰好属于一个小组。

学校决定：

• 必须恰好选出 $k$ 名同学，不能多也不能少；
• 被选中的同学的报名费总和不能超过 $W$ 元；
• 对于每个小组，要么小组内所有同学都被选中，要么都不选（不能只选小组中的一部分）。

请你求出：在满足上述要求的前提下，被选中同学的收获值总和最大是多少。如果不存在任何满足条件的选法，输出 -1。

注意：收获值可能为 $0$，报名费一定不小于 $1$ 元。

输入格式

从标准输入读入数据。

第一行三个整数 $n, k, W$。

接下来 $n$ 行，每行两个整数 $c_i, v_i$，依次表示一名同学的报名费与收获值。

接下来一行一个整数 $m$，表示小组个数。

接下来 $m$ 行，每行第一个整数 $s$（$1 \le s \le 2$）表示小组人数，接着 $s$ 个整数表示小组内同学的编号。保证每个同学恰好出现一次。

输出格式

输出到标准输出。

一行一个整数，表示最大的收获值总和；如果不存在满足条件的选法，输出 -1。

样例 1 输入

4 2 10
3 5
4 6
5 7
6 8
2
2 1 2
2 3 4

样例 1 输出

11

样例 1 解释

同学 $1,2$ 是同一个小组，同学 $3,4$ 是同一个小组。

• 选第一组（同学 $1,2$）：人数 $2$，费用 $3+4=7 \le 10$，收获 $5+6=11$；
• 选第二组（同学 $3,4$）：人数 $2$，费用 $5+6=11>10$，不可行；
• 两组都选：人数 $4$，不等于 $k=2$，不可行。

所以最大收获是 $11$。

样例 2 输入

2 1 10
2 5
2 6
1
2 1 2

样例 2 输出

-1

样例 2 解释

两名同学在同一个小组里，只能同时选或同时不选，因此选不出恰好 $1$ 个人，无解。

特殊性质

• 特殊性质 A：所有小组都只有 $1$ 名同学（即没有任何捆绑）。此时小组之间的选择互不影响，问题退化成经典的“恰好选 $k$ 件、费用不超过 $W$”的二维背包。
• 特殊性质 B：所有小组都恰好有 $2$ 名同学（此时 $n$ 是偶数）。此时每个小组是一个整体：每次决策要么不选，要么同时买下两名同学的名额，可以按“把两名同学的费用与收获各自相加”压缩成一件物品来做二维背包。

数据范围与子任务

对全部测试数据，保证 $1 \le k \le n \le 300$，$1 \le W \le 2000$，$1 \le c_i \le W$，$0 \le v_i \le 10^4$，并且所有小组人数为 $1$ 或 $2$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。