Tetris-like Dropping Game Simulation

This is a game similar to Tetris. The game uses a 9 × 9 board and a set of predefined pieces (fragments). There are 4 types of pieces. For each falling piece, you must choose the column where its designated anchor block (the leftmost block in the piece according to the figure) will align horizontally. Once dropped, a piece falls vertically until it collides with an already placed block or reaches the bottom of the board. If at the moment of placement any block of the piece is not completely within the 9 × 9 region, the game ends immediately. After a piece is placed, any row completely filled with blocks is cleared, and all blocks above that row drop down accordingly.

The 4 pieces are defined as follows (each piece is described by a set of coordinates in \(\bigl(r,c\bigr)\) with respect to its anchor block which is assigned coordinate \((0,0)\). All pieces cannot be rotated):

• Type 1: A horizontal bar
  \(\{(0,0),\,(0,1),\,(0,2)\}\)
• Type 2: An L-shaped piece
  \(\{(0,0),\,(1,0),\,(1,1)\}\)
• Type 3: A zigzag piece
  \(\{(0,0),\,(0,1),\,(1,1),\,(1,2)\}\)
• Type 4: A plus-like piece. Its natural coordinates are defined with the anchor not at the top. To fix the anchor as the designated leftmost block, we subtract \((1,0)\) from all coordinates. Thus, the final set is
  \(\{(-1,1),\,(0,0),\,(0,1),\,(0,2),\,(1,1)\}\).

When dropping a piece, its horizontal position is fixed by adding the chosen column (its anchor column) to each piece's column offset. The piece then falls vertically. Formally, if a piece has offsets \(\{(r_i,c_i)\}\), and its anchor is placed at row \(x\) and column \(y\) (with the chosen column \(y\)), then each block occupies cell \((x+r_i,\,y+c_i)\). The piece falls downward as long as every block can move one row lower (i.e. with \(x-1+r_i \ge 1\) and no collision with already placed blocks). Initially, the piece is set as high as possible so that its topmost block is no higher than row 9. (More precisely, if \(R_{max}\) is the maximum row offset of the piece, the initial base row is \(9-R_{max}\).)

The input consists of \(N\) pieces to drop in order. Once a piece fails to drop completely inside the board, the game stops and you should output the number of pieces that have been successfully dropped.

inputFormat

The first line contains a single integer \(N\) (the number of pieces). Each of the next \(N\) lines contains two integers: type and col. type is an integer between 1 and 4 indicating the type of the piece, and col indicates the column at which the anchor block of the piece is to be dropped. Note that columns are numbered from 1 to 9.

outputFormat

Output a single integer: the number of pieces that were successfully dropped before the game ended.

sample

3
1 1
2 1
1 8

2