Diablo

Problem Background

Special for beginners, ^_^

Problem Description

The game protagonist has $n$ magic types, each divided into several levels. The $i$-th magic has $p[i]$ levels (excluding level 0); each level of each magic has an effect value — a $j$-level $i$-type magic has effect value $w[i,j]$. Leveling up a magic requires a corresponding spellbook, which costs gold; the spellbook for the $i$-th magic costs $c[i]$. Little $x$ has only $m$ gold.

Your task is to help little $x$ decide how to buy spellbooks so that the sum of effect values of all magics is maximized. Initially all magics are at level 0 with effect value 0.

Input Format

The first line contains two integers $n,m$ separated by a space.

The following $n$ lines describe the $n$ magics; the $(i+1)$-th line describes the $i$-th magic. Format:

c[i] p[i] w[i,1] w[i,2] ... w[i,p[i]]

Output Format

The first line outputs one integer — the maximum effect value.

Then $n$ lines output your plan: the $(i+1)$-th line contains an integer $v[i]$ — the level to which you decide to learn the $i$-th magic.

If there are multiple solutions, output the one with the least gold spent.

If there are still multiple, output any one.

Sample Input

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

Sample Output

11
1
0
3

Constraints

$0<n\le 100,\ 0<m\le 500,\ 0<p[i]\le 50,\ 0<c[i]\le 10$.

The input data and the final result fit within long long.

Time limit 1s, memory limit 1024KiB for each test case.