Freight Station (APCS 2022-10 Intermediate)

A freight station has a rectangular warehouse with \(R\) rows and \(C\) columns. Rows are numbered from \(0\) to \(R-1\) from top to bottom, and columns are numbered from \(0\) to \(C-1\) from left to right. Initially, every cell is empty.

The station receives \(n\) cargo pieces in order. Each piece consists of square cells and has one of five shapes: A, B, C, D, or E. The following figure shows A through E from left to right. Every orientation is fixed; pieces cannot be rotated or reflected.

Using # for an occupied cell and . for an empty position inside the bounding rectangle of a shape, the five shapes are:

A    B      C     D     E
#    ###    ##    ..#   .#
#           ##    ###   ##
#                       ##
#

The type of piece \(i\) is \(t_i\). There are \(y_i\) rows between its top and the top of the warehouse, so its topmost occupied cell is in row \(y_i\). Its vertical position never changes while it moves.

A piece first tries to enter completely from the right side of the warehouse, then moves left one column at a time:

1. First, try the rightmost position in which the entire piece is inside the warehouse.
2. If that position is outside the warehouse or overlaps an already placed piece, the new piece cannot enter and is discarded.
3. Otherwise, keep moving it one column left while the next position remains inside the warehouse and does not overlap another piece.
4. When the next move is impossible, fix the piece at its current position.

A piece cannot pass through another piece or reach a hole behind an obstacle. The following figure shows a B piece whose top is two rows below the warehouse top being pushed from right to left.

Discarding a piece does not change the warehouse. Process all pieces in input order, then output the number of empty cells and the number of discarded pieces.

Input

The first line contains three integers \(R\), \(C\), and \(n\): the number of rows, the number of columns, and the number of cargo pieces.

Each of the next \(n\) lines contains an uppercase letter \(t_i\) and an integer \(y_i\), the type and topmost row of piece \(i\).

Constraints

• \(1\le R\le30\)
• \(1\le C\le50\)
• \(1\le n\le200\)
• \(t_i\) is one of A, B, C, D, and E
• \(0\le y_i\)
• Every piece fits vertically: \(y_i+\operatorname{height}(t_i)\le R\)

The shape heights are:

Output

Output two space-separated integers on one line:

number of empty cells number of discarded pieces

Scoring

Sample Input 1

5 4 6
B 0
B 3
B 1
B 3
B 1
B 2

Sample Output 1

8 2

Sample Explanation 1

Every B piece consists of three horizontally adjacent cells.

1. B 0 is placed in columns 0 through 2 of row 0.
2. B 3 is placed in columns 0 through 2 of row 3.
3. B 1 is placed in columns 0 through 2 of row 1.
4. The second B 3 would need three more cells, but the warehouse has only four columns, so it is discarded.
5. The second B 1 is discarded for the same reason.
6. B 2 is placed in columns 0 through 2 of row 2.

The final warehouse is:

###.
###.
###.
###.
....

There are 8 empty cells and 2 discarded pieces.

Sample Input 2

5 6 6
C 1
A 1
E 0
E 0
B 0
A 0

Sample Output 2

13 2

Sample Explanation 2

The animation below simulates the six pieces in order. A collision mark means that the piece cannot enter the warehouse completely and is then discarded.

1. C 1 occupies rows 1 through 2 and columns 0 through 1.
2. A 1 moves as far left as possible and occupies column 2 in rows 1 through 4.
3. The first E 0 is stopped by existing cargo. It occupies \((0,4)\), \((1,3)\), \((1,4)\), \((2,3)\), and \((2,4)\).
4. The second E 0 cannot enter completely, so it is discarded.
5. B 0 collides with \((0,4)\) at the entrance and cannot pass into the hole on the left, so it is discarded.
6. A 0 is placed in column 5 of rows 0 through 3.

The final warehouse is:

....##
######
######
..#..#
..#...

The placed pieces occupy \(4+4+5+4=17\) cells, leaving \(5\times6-17=13\) empty cells. Two pieces are discarded.

Source

APCS October 2022, Programming Task 2; ZeroJudge j123, Freight Station; explanation by Yi-Che Wang.