当前有 N 种物品，第 i 种物品的体积是$c_i$，价值是 $w_i$。

每种物品有且仅有一件。与 01 背包问题的不同的是，这些物品被分为 K 组，每组之间的物品不能同时放入背包内。

现有容量为 V 的背包，请你放入若干物品，使得在背包内的物品不互相冲突的基础上，总体积不超过 V，且总价值尽可能大。

输入格式

输入的第一行，两个整数K、V，表示 有 K 组物品 $(1 \leq K、V \leq 100)$ 。 接下来输入K组物品信息，对于每一组物品的输入如下： 输入一行，一个整数$n_i$表示第i组物品的个数， 接下来$n_i$行，每行两个整数$w_j$、$c_j$，表示第 i 组第j件物品的体积是 $c_j$，价值是 $w_j$

输出格式

输出包括一行，仅一个整数， 为背包中最多可以放入的物品总价值。

样例输入

3 10
2
6 4
7 5
1
7 3
3
6 2
5 1
7 4

样例输出

20