Over Fitting (Large)

Big data is in fashion, and everyone is trying to learn machine learning and data science. Dongi studied data mining and machine learning in a hurry, and now he wants to design an algorithm that finds a linear classifier for a given set of data.

A linear classifier is the equation of a line that correctly separates the types of the data by the two feature values $x_1$ and $x_2$ that a record carries. Many algorithms have been developed to find the best such line automatically for a given set of data.

The data above can be split into two groups exactly by a linear classifier.

The lines $H_1$ and $H_2$ separate the white group from the black group completely by the two features $x_1$ and $x_2$, so they are good classifiers. $H_3$ cannot separate the two groups with a single line, so it is not a good classifier.

A linear classifier that separates the data exactly does not always exist. Real data has many exceptions and errors, and a linear classifier is too simple for it.

Dongi surveyed $N$ people, collecting two feature values for each person and the girl group that person likes most. From this data he wants to find a linear classifier that picks out the people who like Lovelyz most. The linear classifier Dongi is looking for has to satisfy the conditions below.

• The linear classifier splits the data into the two groups Positive and Negative by the feature values.
• You may decide freely which side of the line counts as Positive and which side counts as Negative.
• The Positive group must contain only people who answered that they like Lovelyz most.
• The fewer Lovelyz fans fall into the Negative group, the better the linear classifier is.

Dongi planned to apply various algorithms so that a computer finds the optimal linear classifier automatically. Before that, he became curious about how well the theoretically optimal linear classifier under the conditions above performs on the data he has. Only then can he evaluate the classifier his program finds by comparing it with that number.

Given the data Dongi will use to build a linear classifier, write a program that computes how many of the people who like Lovelyz most the best linear classifier puts into the Positive group.

The linear classifier that puts the most white points into Positive is $L$.

In the figure above, a white point is a person who answered that Lovelyz is their favorite, and a black point is a person who chose another group. The classifier that puts the most white points into Positive is the best one, so taking the line $L$ with the lower side as Positive and the upper side as Negative gives the best linear classifier. The answer here is 7.

The first line contains the number of survey records $N$ ($6 \le N \le 5000$). Each of the next $N$ lines contains one record in the format x1 x2 NAME ($-10^9 \le x_1, x_2 \le 10^9$, the length of NAME is at least 1 and at most 15). $x_1$ and $x_2$ are integers describing the two features of that person, and the group name is given in uppercase letters with no spaces.

A person who answered that Lovelyz is their favorite always has the group name LOVELYZ. At least 3 people like Lovelyz most, and at least 3 people do not.

When the features of each person are taken as coordinates and the data is drawn on the plane, no three or more points lie on one line.

Print on one line how many of the people who like Lovelyz most the optimal linear classifier puts into the Positive group.