Maximum Holstein Enclosure

The farm contains N cows located at distinct points in the 2D plane, where N satisfies \(1 \le N \le 500\). Each cow is of one of two breeds: Holstein or Guernsey. Farmer John wants to build an axis‐aligned rectangular fence that encloses only Holsteins (a cow is considered enclosed even if it lies exactly on the boundary) and does not enclose any Guernseys. Among all such fences, he wishes to enclose the maximum number of Holsteins; and among all fences that enclose this maximum number, he wants the fence with the minimum possible area. Note that a fence with zero width or height is allowed. Your task is to determine this minimum area.

The problem can be formulated mathematically as follows. Let a valid fence be defined by boundaries \(x = L\), \(x = R\), \(y = B\) and \(y = T\) with \(L \le R\) and \(B \le T\). The fence encloses a cow at \((x, y)\) if \(L \le x \le R\) and \(B \le y \le T\). A fence is valid if it encloses no Guernseys. Among all valid fences the objective is to:

[ \begin{array}{ll} \text{maximize} & count(H) \ \text{minimize} & (R - L) \times (T - B) \quad \text{subject to enclosing the maximum count of Holsteins.} \end{array} ]

HTML formatting is used in this description and all formulas are in LaTeX format.

inputFormat

The first line contains an integer \(N\) \( (1 \le N \le 500)\), the number of cows. Each of the next \(N\) lines contains two integers and a character: the x-coordinate, the y-coordinate, and the breed of a cow. The breed is given as 'H' for Holstein or 'G' for Guernsey. All cow positions are distinct.

outputFormat

Output a single integer representing the minimum possible area of a valid fence that encloses the maximum number of Holsteins while enclosing no Guernseys. If no Holsteins can be enclosed without including a Guernsey, output 0.

sample

4
0 0 H
0 1 H
1 0 G
1 1 H

0