#2861. 暗黑破坏神

暗黑破坏神

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

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

i+1\red{i+1 }行有一个整数 v[i]\red{v[i] }表示你决定把第 i\red{i }个魔法学到 v[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

提示

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

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

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

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

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

周日上午少年宫

未参加
状态
已结束
规则
IOI
题目
4
开始于
2022-10-16 9:30
结束于
2022-10-17 15:30
持续时间
30 小时
主持人
参赛人数
7