Заданы координаты N коров ФД (1 <= N <= 500) на 2D-плоскости.
Коровы принадлежат двум разным породам: Holsteins и Guernseys.
ФД хочет построить прямоугольную изгородь со сторонами,
параллельными осям координат, содержащими только коров
Holsteins, без Guernseys (корова считается находящейся в этой области,
Даже если она находится на её границе). Среди всех таких изгородей
ФД хочет выбрать ту, которая будет содержать максимальное количество
коров породы Holsteins. А среди всех таких изгородей ФД хочет выбрать
изгородь с минимальной площадью. Пожалуйста, определите эту площадь.
Допускается изгородь с нулевой высотой или нулевой шириной.
Формат входных данных
Первая строка ввода содержит целое число N. Каждая из следующих N
строк описывает корову двумя целыми числами и одним символом.
Целый числа указываю координаты коровы (x,y) (0 <= x, y <= 1000),
А символ H или G - определяет породу этой коровы. Никакие две коровы
не могут находится в одной точке. И есть хотя бы одна корова типа Holstein.
Формат выходных данных
Выведите два целых числа. Первая строка должна содержать максимальное
число коров породы Holsteins, которые можно огородить так, чтобы
там не было ни одной коровы типа Guernseys. Вторая строка должна содержать
минимальную площадь, огороженную этой изгородью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 H
2 2 H
3 3 G
4 4 H
6 6 H
|
2
1
|