|
|
|
|
描述 Description |
|
|
|
在复杂的社会生活中，TT发现自己有了很多个情敌。为了自己能在感情事业上一帆风顺，TT决定在有限的时间里消灭掉他的情敌，使剩下的情敌对他的威胁最小。
TT有N个情敌，每一个情敌对他都有一个威胁值，消灭他也需要一个时间。但是TT的时间是有限的，他要在两个月内解决掉一些情敌，使得剩下的发敌对他的威胁最小。
但是，情敌们也不会束手待弊，他们也在不断得使自己变强，所以在第二个月，消灭情敌所需要的时间为第一个月的2倍。
或许，情敌们认为这样还是不够强大，所以他们决定选择M个情敌变为超级情敌，超级情敌可以保护一些普通情敌，换句话说想消灭超级情敌所保护的普通情敌，必须先消灭该超级情敌。一个普通情敌最多只能被一个超级情敌所保护。
现在TT想知道，该消灭哪些情敌才能使自己所受到的威胁最少。
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行为两个数字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个数，即他所保护的普通情敌序号。
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
输出一个数字Min，表示TT所受到的最小的威胁。
|
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各个测试点1.5s
|
|
|
|
|
|
|
|
注释 Hint |
|
|
|
对于30%的数据，N<=10，M=0，0<a,b<21。
对于100%的数据，N<=50，M<=4，0<a,b<101。
|
|
|
|
|
|
|
|
来源 Source |
|
|
|
Rgt 原创
NOIP 2009·Dream Team 模拟赛 第一期 第二题
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1628 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
