/ Vijos / 题库 /

情敌

情敌

描述

在复杂的社会生活中,TT发现自己有了很多个情敌。为了自己能在感情事业上一帆风顺,TT决定在有限的时间里消灭掉他的情敌,使剩下的情敌对他的威胁最小。

TT有N个情敌,每一个情敌对他都有一个威胁值,消灭他也需要一个时间。但是TT的时间是有限的,他要在两个月内解决掉一些情敌,使得剩下的发敌对他的威胁最小。

但是,情敌们也不会束手待弊,他们也在不断得使自己变强,所以在第二个月,消灭情敌所需要的时间为第一个月的2倍。

或许,情敌们认为这样还是不够强大,所以他们决定选择M个情敌变为超级情敌,超级情敌可以保护一些普通情敌,换句话说想消灭超级情敌所保护的普通情敌,必须先消灭该超级情敌。一个普通情敌最多只能被一个超级情敌所保护。

现在TT想知道,该消灭哪些情敌才能使自己所受到的威胁最少。

格式

输入格式

第一行为两个数字a,b,表示TT第一个月和第二个月的时间。

第二行为两个数字N,M,表示TT有N个情敌,其中M个是超级情敌。

第3到第N+2行,每I行有两个数字x,t,表示第I-2个情敌对TT的威胁值和TT消灭他所需要的时间。

第N+3行到第N+2+M行,前两个数c,tot,表示第c个情敌是超级情敌,他保护的普通情敌有tot个,后面给出tot个数,即他所保护的普通情敌序号。

输出格式

输出一个数字Min,表示TT所受到的最小的威胁。

样例1

样例输入1

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

样例输出1

15

限制

各个测试点1.5s

提示

对于30%的数据,N<=10,M=0,0<a,b<21。

对于100%的数据,N<=50,M<=4,0<a,b<101。

来源

Rgt 原创
NOIP 2009·Dream Team 模拟赛 第一期 第二题

信息

ID
1628
难度
8
分类
动态规划 | 树形DP动态规划 | 背包 点击显示
标签
(无)
递交数
919
已通过
132
通过率
14%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

NOIP 2009 Dream Team 模拟赛 第一期