题目描述

无聊中的小 $\red{x }$玩起了 $\red{Diablo I...}$ 游戏的主人公有 $\red{n }$个魔法 每个魔法分为若干个等级，第 $\red{i }$个魔法有 $\red{p[i]}$个等级$\red{(}$不包括 $\red{0)}$

每个魔法的每个等级都有一个效果值，一个 $\red{j }$级的 $\red{i }$种魔法的效果值为 $\red{w[i][j]}$ 魔法升一级需要一本相应的魔法书 购买魔法书需要金币，第 $\red{i }$个魔法的魔法书价格为 $\red{c[i]}$

而小 $\red{x }$只有 $\red{m }$个金币$\red{(}$好孩子不用修改器$\red{)}$ 你的任务就是帮助小 $\red{x }$决定如何购买魔法书才能使所有魔法的效果值之和最 大 开始时所有魔法为 $\red{0 }$级 效果值为 $\red{0}$

输入格式

第一行 用空格隔开的两个整数 $\red{n m}$

以下 $\red{n }$行 描述 $\red{n }$个魔法

第 $\red{i+1 }$行描述 第 $\red{i }$个魔法 格式如下 $\red{c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]}$

输出格式

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

以后 $\red{n }$行输出你的方案：

第 $\red{i+1 }$行有一个整数 $\red{v[i] }$表示你决定把第 $\red{i }$个魔法学到 $\red{v[i]}$级

如果有多解 输出花费金币最少的一组

如果还多解 输出任意一组

样例

输入样例

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

输出样例

11
1
0
3

提示

$\red{0<n<=100}$

$\red{0<m<=500}$

$\red{0<p[i]<=50}$

$\red{0<c[i]<=10}$

保证输入数据和最终结果在 $\red{longint }$范围内