题目描述

农夫约翰的奶牛们非常喜欢玩电子游戏！FJ 发现，在玩了这些游戏后，他的奶牛产的奶比平时多得多，这肯定是因为快乐的奶牛产奶更多。

然而，奶牛们对于哪个是最好的游戏机存在分歧。一头奶牛想买 Xbox 360 来玩《光环 3》；另一头想买任天堂 Wii 来玩《任天堂明星大乱斗》；第三头想在 PlayStation 3 上玩《合金装备 4》。FJ 想购买一些游戏机（每种不超过一台）和游戏（每种不超过一款并在给定预算的限制内），以帮助他的奶牛产出最多的牛奶，从而养育更多的孩子。

FJ 调查了 $N$ 台游戏机（$1 \leq N \leq 50$），每台游戏机的价格为 $P_i$（$1 \leq P_i \leq 1000$），以及独占发布于该游戏机的游戏数量 $G_i$（$1 \leq G_i \leq 10$）。当然，奶牛必须先拥有这台游戏机，才能购买该游戏机独占的任何游戏。每款游戏都有一个游戏价格 $GP_j$（$1 \leq GP_j \leq 100$）和一个生产值（$1 \leq PV_j \leq 1,000,000$），表示奶牛在玩游戏后会产出多少牛奶。最后，农夫约翰有一个预算 $V$（$1 \leq V \leq 100,000$），这是他最多能花的钱。帮助他最大化他购买的游戏的生产值之和。

考虑一个例子，$N=3$ 台游戏机，预算 $V=800$ 美元。

第一台游戏机价格为 $300$ 美元，并有两个游戏，价格分别为 $30$ 美元和 $25$ 美元，生产值如下所示：

第二台游戏机价格为 $600$ 美元，只有一个游戏：

第三台游戏机价格为 $400$ 美元，有三个游戏：

农夫约翰应该购买游戏机 $1$ 和 $3$，游戏机 $1$ 的游戏 $2$，以及游戏机 $3$ 的游戏 $1$ 和 $3$，以最大化他所购买游戏的生产值。该值为 210：

生产值
        预算:      $800      
        游戏机 1  -$300
          游戏 2  -$25              80
        游戏机 3  -$400
          游戏 1  -$40              70
          游戏 3  -$35              60
      -------------------------------------------
        总计:        0 (>= 0)      210

输入格式

输入第 $1$ 行为两个用空格分隔的整数：$N$ 和 $V$

第 $2$ 到 $N+1$ 行：第 $i+1$ 行描述了游戏机 $i$ 的价格 $P_i$ 和其独占的游戏数量 $G_i$，接下来后面有 $G_i$ 对用空格分隔的整数 $GP_j$ 和 $PV_j$，描述其独占的各款游戏的信息。

输出格式

输出 $1$ 个整数，表示农夫约翰在他的预算内可以获得的最大生产值。

输入输出样例 #1

输入 #1

3 800 
300 2 30 50 25 80 
600 1 50 130 
400 3 40 70 30 40 35 60

输出 #1

210