Red Points and Blue Points

Time limit1sMemory limit128 MB

Summary

Given red and blue points on a plane, find two parallel lines (avoiding all points, excluding all blue points from the strip) that maximize red points strictly between them.

Level: Hard8 of 10
Topics: Geometry, Binary search, Sorting
Solved: No attempts yet

Problem

There are red points and blue points on a coordinate plane. You will draw two parallel lines to protect red points that lie strictly between them. No blue point may lie between the two lines, and neither line may pass through any point.

It may be impossible to protect every red point. Find the maximum number of red points that can be protected by choosing two such parallel lines.

Input

The first line contains the number of points N. (1 ≤ N ≤ 1000)

Each of the next N lines contains a point's x-coordinate, y-coordinate, and color, separated by spaces. Each coordinate is an integer whose absolute value is less than 10^9, and the color is either R or B.

No three points are collinear.

Output

Print the maximum number of red points that can be protected by two parallel lines satisfying the conditions.

Examples2

Example 1
Input
```
4
0 0 R
0 1 B
1 1 R
1 0 B
```
Expected output
```
2
```

Example 2

Input

8
2 -3 R
4 -1 R
-2 0 R
-3 1 B
-2 3 R
1 4 R
2 1 B
0 -3 B

Expected output