分组 (group)
题目描述
随着经济全球化的发展，会社的制药业务也越做越大，员工也越来越多。现在，作为会社社长的你，想要将公司内的员工划分成两个非空小组，营造公司内部的良性竞争，激发员工制作钙片的热情。公司内部有许多由少数员工构成的小团体，如果这个小团体的所有员工都被分到同一个小组，那么就会产生一定量的效益。你需要设计一种划分方案，使得获得的总效益最高。
具体的说，公司内部一共有 名员工和 个小团体，第 个团体的人数为 ，效益为 .
输入格式
第一行两个正整数 表示员工数量和小团体数量
接下来依次描述个小团体。
每个小团体第一行两个正整数 ，表示人数和效益。
第二行 个正整数表示团体内部员工编号。
输出格式
一行一个正整数，表示答案。
样例输入 1
4 3
2 4
1 2
2 5
1 3
3 10
2 3 4
样例输出 1
10
样例解释 1
| 第一组 | 第二组 | 总效益 |
|---|---|---|
| {1} | {2，3，4} | 10 |
| {1，2} | {3，4} | 4 |
| {1，2，3} | {4} | 9 |
| {1，3} | {2，4} | 5 |
| {2} | {1，3，4} | |
| {2，3} | {1，4} | 0 |
| {3} | {1，2，4} | 4 |
样例输入 2 / 样例输出 2
见下发文件
数据范围与提示
Subtask 1 (7 pts)
Subtask 2 (24 pts)
Subtask 3 (31 pts)
Subtask 4 (38 pts)
无特殊限制
对于所有数据，$2\le n\le 40,1\le m\le 500,2\le k_i\le 3,1\le f_i\le 10^9$