Holstein Fence

Time limit1sMemory limit256 MB

Summary

Enclose the most Holsteins in an axis-aligned rectangle with no Guernsey inside, breaking ties by smallest area.

Level: Medium6 of 10
Topics: Brute force, Sorting, Geometry
Solved: No attempts yet

Problem

There are $N$ cows ( $1 \le N \le 500$ ) standing on the plane at distinct points. Each cow is either a Holstein or a Guernsey.

The farmer wants to build a rectangular fence with sides parallel to the coordinate axes so that it encloses only Holsteins and no Guernsey at all. A cow on the boundary of the fence counts as enclosed.

Among all such fences, pick the one that encloses the most Holsteins, and among those, pick the one with the smallest area. Report the number of enclosed Holsteins and that area. A fence of width or height $0$ is allowed.

Input

The first line contains $N$ .

Each of the next $N$ lines contains two integers $x$ , $y$ ( $0 \le x, y \le 1000$ ) and one character. $(x, y)$ is where the cow stands, and the character gives the breed: H for a Holstein, G for a Guernsey.

No two cows stand at the same point, and at least one cow is a Holstein.

Output

On the first line, print the maximum number of Holsteins that a fence enclosing no Guernsey can enclose.

On the second line, print the smallest area among those fences.

Examples3

Example 1
Input
```
5
1 1 H
2 2 H
3 3 G
4 4 H
6 6 H
```
Expected output
```
2
1
```
Example 2
Input
```
1
0 0 H
```
Expected output
```
1
0
```

Example 3

Input

Expected output

3
1