题目描述

有$N$个物品，物品个数为$A_i$（$A_i$为0则无个数限制），价值为$W_i$，体积为$C_i$，给出$G$组限制，每组中的物品最多只能取一种，问物品体积刚好为$D$时，最大价值是多少

输入格式

第一行两个整数$N$和$D$。 接下来$N$行，每行$3$个整数$A_i$，$W_i$，$C_i$ 。 第$N+2$行一个非负整数 $G$ 。 接下来$G$行，开头一个整数$L$，表示组的大小，然后$L$个整数，表示该组的物品编号，保证每个物品最多出现在一组中。

输出格式

输出一个整数表示最大的价值。若最大价值为负或无法满足体积恰好为D，则输出i'm sorry...

4 10
2 4 3
1 4 2
3 1 2
2 3 1
1
2 2 4

15

2 1024
0 1 3
0 0 1
0

341

2 5
0 1 2
0 2 4
0

i'm sorry...

10 1023
1 1 1
1 1 2
1 1 4
1 1 8
1 1 16
1 1 32
1 1 64
1 1 128
3 -1 256
1 1 512
1
2 9 10

5

10 1023
1 1 1
1 1 2
1 1 4
1 1 8
1 1 16
1 1 32
1 1 64
1 1 128
1 1 256
1 1 512
1
2 9 10

i'm sorry...

提示

1<=N<=1024, 0<=D<=1024. 0<=Ai<=1024, -1024<=Ci<=1024, 0<Vi<=D 0<=G<=8

样例1解释： 取2个1号物品，1个3号物品和2个4号物品（取了4号物品之后，不能再取2号物品） 样例2解释： 取341个1号物品 样例3解释： 无法构成5的体积