Maximum Red Points in a Blue-Free Strip

You are given N points in the plane. Each point is colored either red or blue (denoted by 'R' or 'B'). No three points are collinear. Your task is to find a pair of parallel lines (which can have any orientation, not necessarily parallel to the coordinate axes) that do not pass through any point and such that there is no blue point strictly between them. Among all such pairs of parallel lines, you must choose the one that maximizes the number of red points strictly between them, and output this maximum count.

Note: The parallel lines cannot go through any of the points. However, an optimal configuration can be approached arbitrarily close to one or more points. In other words, if a line would go through a point, you can always slightly perturb it without changing the set of enclosed red points or including a blue point inside.

Hint: One way to think about this problem is to choose an orientation for the lines. Once an orientation is fixed, project every point onto the normal direction. Then, the problem reduces to choosing an interval (which must fall into a gap of blue point projections) that contains as many red point projections as possible.

inputFormat

The first line contains an integer N (the number of points). Each of the next N lines contains three items: the x-coordinate, the y-coordinate and the color of the point. The color is given as a single character: 'R' denotes a red point and 'B' denotes a blue point.

No three points are collinear.

outputFormat

Output a single integer: the maximum number of red points that can be enclosed between two parallel lines that (1) do not pass through any point, and (2) have no blue point strictly between them.

sample

5
0 0 R
1 0 R
0 1 R
1 1 B
2 2 R

2