外接圆在 MINISO 买装饰品,超市里有 n 个挂件,每个挂件上有它们自己的挂件。如果要买挂件上的挂件,就要先买挂挂件的挂件。
也就是说,对于第 i 个商品,有 m_i 个附属品,只有购买了第 i 个商品,才能购买这 m_i 个附属品。
每件商品和附属品都有它的价格和体积。
外接圆带了个容积有限的包,他想在购买的物品不超过包包容积的条件下花掉尽可能多的钱。
输入的第一行两个正整数 n,V ,分别表示商品的数量和包包的容积。
接下来输入 n 个物品,每个物品的输入占 m_i+1 行。
其中第一行三个正整数 w_i,v_i,m_i ,分别表示第 i 个物品的价值、体积和附属品数量。
接下来 m_i 行,每行两个正整数 c_j,u_j ,分别表示物品 i 的第 j 个附属品的价值和体积。
输出一行一个整数,表示花掉的钱数最多是多少。
3 103 2 22 23 24 3 11 22 3 13 1
13
1\le n\le 100
1\le V\le 100
1\le m_i\le 10
1\le w_i,c_j\le 1000
1\le v_i,u_j\le V