만인을 위한 지식

철로 위를 움직이는 책장이 놓인 도서관에 있습니다. 철로는 여러 개가 평행하게 놓여 있어, 책장은 아래 그림처럼 여러 줄(row)로 나뉘어 정리되어 있습니다.

도서관에 놓인 책장들. 지금은 사서에게 갈 수 있는 통로가 없습니다.

책을 빌리려면 책장 반대편에 숨어 있는 사서를 찾아가야 합니다. 그러려면 책장들을 철로를 따라 밀어 통로를 만들어야 합니다.

• 각 책장은 정수 너비를 가지며, 철로 위 임의의 정수 위치에 놓을 수 있습니다. (정수가 아닌 위치에서는 고정되지 않아 어느 쪽으로든 굴러갈 수 있습니다.)
• 한 줄 안의 책장들이 서로 붙어 있을 필요는 없습니다. 이웃한 두 책장 사이에는 임의의 (정수) 크기의 빈 공간이 있을 수 있습니다.
• 한 줄 안에서 책장들은 서로 겹칠 수 없고, 서로를 통과할 수 없어 좌우 순서가 바뀌지 않습니다.

위치 $k$에 통로가 생겼다는 것은, 모든 줄에서 구간 $(k, k+1)$ 안에 어떤 책장도 없다는 뜻입니다.

통로가 만들어진 모습: 왼쪽 그림은 위치 $8$, 오른쪽 그림은 위치 $9$입니다. 화살표로 표시된 책장을 밀어, 두 경우 모두 비용 $3$으로 통로를 만들었습니다.

책장 하나를 미는 데는 노력이 듭니다. 어느 방향으로 밀든 한 번 미는 비용은 $1$이며, 이 비용은 미는 거리와 무관합니다(정지 마찰이 운동 마찰보다 훨씬 크다는 잘 알려진 사실로 설명할 수 있습니다). 운동을 하러 온 것이 아니라 책을 빌리러 왔으니, 되도록 적은 노력으로 (어느 위치든) 통로 하나를 만들고 싶습니다.

각 줄에서 값이 양수 $a_{i,j} > 0$이면 너비가 $a_{i,j}$인 책장을, $a_{i,j} = 0$이면 폭이 $1$인 빈 공간을 나타냅니다.

• 첫 줄에 테스트 케이스의 수 $Z$ ($Z \le 15$)가 주어집니다. 이어서 $Z$개의 테스트 케이스가 주어집니다.
• 각 테스트 케이스의 첫 줄에는 두 정수 $R$과 $L$ ($1 \le R$, $1 \le L \le 10^6$)이 공백으로 구분되어 주어집니다. 각각 줄의 개수와 모든 줄의 공통 너비입니다.
• 이어서 $R$개의 줄 설명이 주어집니다. 각 줄은 정수 $n_i$로 시작하고, 그 뒤에 $n_i$개의 정수 $a_{i,1}, a_{i,2}, \dots, a_{i,n_i}$가 공백으로 구분되어 옵니다.

모든 줄 $i$에 대해 $\sum_j a_{i,j}$는 $L$에서 값이 $0$인 $a_{i,j}$의 개수를 뺀 값과 같습니다. 또한 $n_1 + n_2 + \dots + n_R \le 2 \times 10^7$입니다. 각 줄의 설명에는 $0$이 적어도 하나 있으므로, 통로를 만드는 것은 항상 가능합니다.

각 테스트 케이스마다 두 줄을 출력합니다.

• 첫 줄에는 통로를 만드는 데 필요한 최소 비용을 출력합니다.
• 둘째 줄에는 최소 비용으로 통로를 만들 수 있는 모든 위치를 증가하는 순서로 공백으로 구분하여 출력합니다.