题面描述

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

输入格式

第一行两个整数N和 D。

接下来N行，每行3个整数Ai，Wi，Ci 。

第N+2行一个非负整数 G 。

接下来G行，开头一个整数L，表示组的大小，然后L个整数，表示该组的物品编号，保证每个物品最多出现在一组中。

输出格式

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

样例
输入1

4 10
2 4 3
1 4 2
3 1 2
2 3 1
1
2 2 4
输出1
15
输入2
2 1024
0 1 3
0 0 1
0
输出2
341
输入3
2 5
0 1 2
0 2 4
0
输出3
i'm sorry...
输入4
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
输出4
5
输入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
输出5
i'm sorry...

数据范围与提示
1<=N<=1024, 0<=D<=1024.
0<=Ai<=1024, -1024<=Wi<=1024, 0<Ci<=D
0<=G<=8


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