AI Tetris (Small)

Dongi is a beginner game developer, and he is building his own Tetris game. Tetris is played on a board with 20 rows and 10 columns. A block shape falls from the top, and the player rotates it or shifts it left and right while stacking it up. When a block can fall no further and stops, every row that is completely filled is deleted, and the player gets 1 point for each deleted row. The rows above a deleted row keep their shape and come down. There are seven block shapes, and each one can be rotated by 90, 180 or 270 degrees.

An example of the 20 by 10 board (left) and the seven Tetris block shapes (right)

The rules of Tetris are simple, so Dongi finished the game quickly. He wants to test it by playing it himself, but his hands are slow and he cannot clear anything above a certain difficulty on his own. So he wrote a cheat feature for himself.

• The block shape he is controlling right now disappears from the board.
• Dongi cannot control the next block shape. It appears at the best position by itself and travels along the best path.
• The shape that appears and its orientation are picked from all seven shapes and all of their rotations, so that the number of deleted rows is as large as possible.
• While the shape falls it never changes from the form it appeared in, and it never rotates. The best shape is picked under that restriction.

On the board in the picture the cheat makes the 4 by 1 long bar appear in the rightmost column and fall straight down. That deletes two rows and gives 2 points. No other shape deletes more than two rows.

You are given the current state of the board. Write a program that computes the largest number of rows the cheat feature can delete. The top four rows of the board are always empty.

The input has 20 lines that give the state of each row of the board. Each line is a string of length 10 made of 0 and 1 only, where 0 is an empty cell and 1 is a cell filled with a block.

The line that comes first is the upper row of the board. The first four lines from the top are always filled with 0 only.

Every row has at least one empty cell.

The board given in this problem is shaped so that the largest number of rows can be deleted without shifting the block left or right while it falls.

Print the largest number of rows the cheat feature can delete on one line.

The first example uses the same board as the picture in the statement. Standing the long bar in the rightmost column and dropping it deletes two rows. In the second example only the leftmost cell of each of the bottom four rows is empty, so the same bar deletes four rows at once.