Slicing Tree

VLSI circuits are so complex, reaching millions of transistors in a single chip today, that they cannot be designed without CAD tools. To reduce the complexity of the design process, the whole flow is broken into several intermediate phases, one of which is the physical design phase. In physical design the basic components of a circuit are usually treated as rectangular modules. Within this phase there are several steps, and the one most critical to circuit performance is the floorplan/placement step. The real floorplan/placement problem is very complex, so here you only handle a simplified version in which every component is viewed as a single rectangle in the plane.

The simplified problem is to place $n$ rectangles in the plane, all axis-parallel, so that a set of given constraints is satisfied. The constraints describe relative locations between rectangles. A relative location means that rectangle $R_i$ ($1 \le i \le n$) must be placed either below (or above) rectangle $R_j$ ($1 \le j \le n$), or to the left (or right) of it. For each rectangle $R_i$, the coordinates of its lower-left corner and its upper-right corner are written as $(x_i^{ll}, y_i^{ll})$ and $(x_i^{ur}, y_i^{ur})$. Saying that $R_i$ is below $R_j$ means $y_i^{ur} \le y_j^{ll}$, and saying that $R_i$ is to the left of $R_j$ means $x_i^{ur} \le x_j^{ll}$. Each rectangle may also be placed rotated by $90^\circ$. Note that a single constraint such as "$R_1$ is below $R_2$" can still be satisfied by more than one placement.

The relative-location constraints are represented by a binary tree called a slicing tree. A slicing tree describes how the plane is partitioned and which rectangle goes into each sub-region. Every internal node is labeled either $H$ or $V$, and every external node (leaf) is labeled with a rectangle identification number $i$ ($1 \le i \le n$). Label $H$ means the sub-region is partitioned by a horizontal line, and label $V$ means it is partitioned by a vertical line. For instance, in a tree with only two leaves, a root labeled $H$ means $R_1$ must be placed below $R_2$, while a root labeled $V$ means $R_1$ must be placed to the left of $R_2$.

In general, if an internal node $N_k$ is labeled $H$, then every rectangle in the left subtree of $N_k$ must be placed below every rectangle in the right subtree. Likewise, if $N_k$ is labeled $V$, every rectangle in the left subtree must be placed to the left of every rectangle in the right subtree.

Once a placement is fixed, let $\boxed{R}$ denote the minimum rectangle that encloses all the rectangles. Given a slicing tree and the dimensions of the rectangles, your program must determine a location (and orientation) for each rectangle so that all constraints are satisfied and the area of the enclosing rectangle $\boxed{R}$ is as small as possible. Note that the area of $\boxed{R}$ can depend on the orientation chosen for each rectangle.

Your program reads from standard input. The input consists of $T$ test cases, and the number of test cases $T$ is given on the first line.

Each test case begins with a line containing an integer $n$ ($1 \le n \le 1000$), the number of rectangles. The next $n$ lines give the dimensions of the rectangles, one per line. The $i$-th line ($1 \le i \le n$) contains two integers $w$ and $h$ ($1 \le w, h \le 500$), the width and height of rectangle $i$.

The following line describes the slicing tree. It is a list of $2n - 1$ items separated by spaces, obtained by traversing the slicing tree in post-order. Each item is either an internal-node label or an external-node label. An internal-node label is $H$ or $V$, and an external-node label is an integer $i$ ($1 \le i \le n$), the rectangle identification number.

Your program writes to standard output. Print exactly one line for each test case. For each test case, find a placement that satisfies all relative-location constraints and minimizes the area of the enclosing rectangle $\boxed{R}$, then print that minimum area on its own line. You may assume that the resulting area of $\boxed{R}$ is less than $10^{10}$ for every test case.