暗黑破坏神

题目描述

小 x 在玩《暗黑破坏神》游戏，游戏的主人公有 $n$ 个魔法。每个魔法分为若干个等级，第 $i$ 个魔法有 $p[i]$ 个等级（不包括 0 级）。每个魔法的每个等级都有一个效果值，一个 $j$ 级的第 $i$ 种魔法的效果值为 $w[i][j]$。魔法升一级需要一本相应的魔法书，购买魔法书需要金币，第 $i$ 个魔法的魔法书价格为 $c[i]$。而小 $x$ 只有 $m$ 个金币（好孩子不用修改器）。

你的任务就是帮助小 $x$ 决定如何购买魔法书才能使所有魔法的效果值之和最大。开始时所有魔法为 0 级，效果值为 0。

输入格式

第一行，用空格隔开的两个整数 $n$、$m$。

以下 $n$ 行，描述 $n$ 个魔法。第 $i+1$ 行描述第 $i$ 个魔法，格式为：$c[i]$ $p[i]$ $w[i][1]$ $w[i][2]$ ... $w[i][p[i]]$。

输出格式

第一行输出一个整数，即最大效果值。

以后 $n$ 行输出你的方案：第 $i+1$ 行有一个整数 $v[i]$，表示你决定把第 $i$ 个魔法学到 $v[i]$ 级。如果有多解，输出花费金币最少的一组；如果还多解，输出任意一组。

样例

样例输入

3 10
1 3 1 2 2
2 3 2 4 6
3 2 1 10

样例输出

11
1
0
3

数据范围与提示

• $0 < n \leq 100$
• $0 < m \leq 500$
• $0 < p[i] \leq 50$
• $0 < c[i] \leq 10$
• 保证输入数据和最终结果在 $\text{longint}$ 范围内