Far Relative’s Problem

题意翻译

Problem 小白想在2019年邀请他的好友参加一次聚会,具体哪一天未确定,但是已知第i个朋友的性别,且该朋友在第a​i​到b​i这几天有时间参加(包含a​i和b​i)。 小白希望参加的朋友的男女数量刚好相等,且能参加的人数越多越好。 当然为了男女人数相等,他也可以婉拒其中的某些人。请计算最多有多少个朋友可以参加。 Input Data 第一行:一个整数n,表示朋友的数量。 接下来n行,分别是一个字符‘F’或者‘M’,分别表示女和男;两个整数,分别表示a​i和b​i。 Output Data 输出共一个数,表示在男女数量相等的情况下,最多可以有多少个朋友参加派对。

题目描述

Famil Door wants to celebrate his birthday with his friends from Far Far Away. He has $ n $ friends and each of them can come to the party in a specific range of days of the year from $ a_{i} $ to $ b_{i} $ . Of course, Famil Door wants to have as many friends celebrating together with him as possible. Far cars are as weird as Far Far Away citizens, so they can only carry two people of opposite gender, that is exactly one male and one female. However, Far is so far from here that no other transportation may be used to get to the party. Famil Door should select some day of the year and invite some of his friends, such that they all are available at this moment and the number of male friends invited is equal to the number of female friends invited. Find the maximum number of friends that may present at the party.

输入输出格式

输入格式


The first line of the input contains a single integer $ n $ ( $ 1<=n<=5000 $ ) — then number of Famil Door's friends. Then follow $ n $ lines, that describe the friends. Each line starts with a capital letter 'F' for female friends and with a capital letter 'M' for male friends. Then follow two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i}<=b_{i}<=366 $ ), providing that the $ i $ -th friend can come to the party from day $ a_{i} $ to day $ b_{i} $ inclusive.

输出格式


Print the maximum number of people that may come to Famil Door's party.

输入输出样例

输入样例 #1

4
M 151 307
F 343 352
F 117 145
M 24 128

输出样例 #1

2

输入样例 #2

6
M 128 130
F 128 131
F 131 140
F 131 141
M 131 200
M 140 200

输出样例 #2

4

说明

In the first sample, friends $ 3 $ and $ 4 $ can come on any day in range $ [117,128] $ . In the second sample, friends with indices $ 3 $ , $ 4 $ , $ 5 $ and $ 6 $ can come on day $ 140 $ .