问题描述

有 ( N ) 组物品和一个容量是 ( V ) 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 ( v_{ij} )，价值是 ( w_{ij} )，其中 ( i ) 是组号，( j ) 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行有两个整数 ( N, V )，用空格隔开，分别表示物品组数和背包容量。

接下来有 ( N ) 组数据：

• 每组数据第一行有一个整数 ( S_i )，表示第 ( i ) 个物品组的物品数量；
• 每组数据接下来有 ( S_i ) 行，每行有两个整数 ( v_{ij}, w_{ij} )，用空格隔开，分别表示第 ( i ) 个物品组的第 ( j ) 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

[0 < N, V < 100]
[0 < S_i < 100]
[0 < v_{ij}, w_{ij} < 100]

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例

8

样例解释

• 第一组物品选择第二个物品（体积2，价值4）。
• 第二组物品选择唯一物品（体积3，价值4）。
• 第三组物品不选。

总价值为 ( 4 + 4 = 8 )，总体积为 ( 2 + 3 = 5 )，满足背包容量限制。