K - Knowledge for the masses

08.01.2010
TrudnośćTrudnośćTrudnośćTrudność

Time limit: 30 s
Memory limit: 32 MB

You are in a library equipped with bookracks that move on rails. There are many parallel rails, i.e., the bookracks are organized in several rows, see figure:


The boockracks in the library. There is no passage to the librarian at the moment.

To borrow a book, you have to find the librarian, who seems to hide on the opposite side of the bookracks. Your task then is to move the racks along the rails so that a passage forms. Each rack has a certain integer width, and can be safely positioned at any integer point along the rail. (A rack does not block in a non-integer position and could accidentally move in either direction). The racks in a single row need not be contiguous — there can be arbitrary (though integer) space between two successive bookracks. A passage is formed at position $ k $ if there is no bookrack in the interval $ (k,k+1) $ in any row (somehow you don't like the idea of trying to find a more sophisticated passage in this maze.)


The passages formed in the library: at position 8 (the left figure) and at position 9 (the right figure). Both attained at cost 3 by moving the bookracks marked with arrows.

Moving a rack requires a certain amount of effort on your part: moving it in either direction costs 1. This cost does not depend on the distance of the shift, which can be explained by a well known fact that static friction is considerably higher than kinetic friction. Still, you are here to borrow a book, not to work out, so you would like to form a passage (at any position) with as little effort as possible.

Multiple Test Cases

The input contains several test cases. The first line of the input contains a positive integer $ Z \leq 15 $, denoting the number of test cases. Then $ Z $ test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.

Single Instance Input

Two space separated integers $ R $ and $ L $ ($ 1\leq R $, $ 1\leq L\le 10^6 $) are given in the first line of an input instance. They denote the number of rows and the width of each and every row, respectively. Then $ R $ lines with rows descriptions follow. Each such line starts with an integer $ n_i $, followed by $ n_i $ integers $ a_{i,1}, a_{i,2}, \ldots a_{i,n_i} $, all separated by single spaces. Number $ a_{i,j} $ denotes either the width of a bookrack when $ a_{i,j}>0 $ or a unit of empty space when $ a_{i,j}=0 $. Note that for any row $ i $, $ \sum_j a_{i,j} $ equals $ L $ minus the number of $ a_{i,j} $ that are equal to zero. You may assume that $ n_1+n_2+\cdots+n_R \leq 2*10^7 $. Moreover, there will be at least one $ 0 $ in the description of each row, which means that creating a passage is always possible.

Single Instance Output

In the first line, your program should output the minimum cost of making a passage through the bookracks. In the second line, it should print out the increasing sequence of all the positions at which a minimum cost passage can be formed.

Example

Input

1
4 10
8 1 2 1 0 1 2 0 1
7 2 2 2 1 0 1 0
6 1 3 2 0 2 1
7 2 1 2 0 2 1 0

Output

3
8 9
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com